# Problem Statement
Given the root to a binary tree where each node has an additional pointer called sibling (or next), connect the sibling pointer to the next node in the same level. The last node in each level should point to the first node of the next level in the tree.

Consider the following binary tree.

Here's how the final tree would look when all sibling pointers have been connected.

<br>

# Hint
* Level order traversal

<br>

# Try it yourself

void populate_sibling_pointers(BinaryTreeNode* root) {
 //TODO: Write - Your - Code
}

#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <algorithm>
#include <assert.h>
#include <time.h>
#include <fstream>
#include <sstream>
#include <limits>
#include <math.h>
#include <stack>
#include <cstdlib>
using namespace std;


struct BinaryTreeNode
{
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode* parent;

    // below data members used only for some of the problems
    BinaryTreeNode* next;
    int count;

    BinaryTreeNode(int d) : data(d), left(nullptr), right(nullptr), next(nullptr), parent(nullptr), count(0) {
    }
};

BinaryTreeNode* insert_bst(BinaryTreeNode* root, int d) {
  BinaryTreeNode* pNew = new BinaryTreeNode(d);
  if (root == nullptr) {
    return pNew;
  }

  BinaryTreeNode* parent = nullptr;
  BinaryTreeNode* pTemp = root;
  while (pTemp != nullptr) {
    parent = pTemp;
    if (d < pTemp->data) {
      pTemp = pTemp->left;
    } else {
      pTemp = pTemp->right;
    }
  }

  if (d < parent->data) {
    parent->left = pNew;
  } else {
    parent->right = pNew;
  }

  return root;
}

BinaryTreeNode* find_in_bst(BinaryTreeNode* root, int d) {
  if(root == nullptr)
    return nullptr;

  if(root->data == d) {
    return root;
  }
  else if( root->data > d)
  {
    return find_in_bst(root->left, d);
  }
  else
  {
    return find_in_bst(root->right,d);
  }
}

BinaryTreeNode* insert_binary_tree(BinaryTreeNode* root, int d) {
  BinaryTreeNode* pNew = new BinaryTreeNode(d);
  if (root == nullptr) {
    return pNew;
  }

  BinaryTreeNode* parent = nullptr;
  BinaryTreeNode* pTemp = root;
  while (pTemp != nullptr) {
    parent = pTemp;
    if (d < pTemp->data) {
      pTemp = pTemp->left;
    } else {
      pTemp = pTemp->right;
    }
  }

  if (rand()%2 == 0) {
    parent->left = pNew;
  }
  else {
    parent->right = pNew;
  }

  return root;
}

BinaryTreeNode* create_BinaryTree(int count) {
  BinaryTreeNode* root = nullptr;
  for (int i = 0; i < count; ++i) {
    int r = rand() % 100;
    root = insert_binary_tree(root, r);
  }
  return root;
}

void display_inorder(BinaryTreeNode* node) {
  if (node == nullptr) {
    return;
  }
  display_inorder(node->left);
  cout << node->data << ", ";
  display_inorder(node->right);
}

void get_inorder(BinaryTreeNode* node, vector<int>& output) {
  if (node == nullptr) {
    return;
  }
  get_inorder(node->left, output);
  output.push_back(node->data);
  get_inorder(node->right, output);
}

void display_preorder(BinaryTreeNode* node) {
  if (node == nullptr) {
    return;
  }
  cout << node->data << ", ";

  display_preorder(node->left);
  display_preorder(node->right);
}

void get_preorder(BinaryTreeNode* node, vector<int>& output) {
  if (node == nullptr) {
    return;
  }
  output.push_back(node->data);
  get_inorder(node->left, output);
  get_inorder(node->right, output);
}

BinaryTreeNode* create_BST(vector<int>& v) {
  BinaryTreeNode* root = nullptr;
  int count = 0;
  for (int x : v) {
    root = insert_bst(root, x);
    if (count % 50000 == 0) {
      cout << "Inserted " << count << endl;
    }
    ++count;
  }
  return root;
}

BinaryTreeNode* create_random_BST(int count) {
  BinaryTreeNode* root = nullptr;
  srand(time(NULL));
  for (int i = 0; i < count; ++i) {
      int r =  rand() % 997;
      root = insert_bst(root, r);
  }
  return root;
}

void binary_tree_to_vector_rec(BinaryTreeNode* root, vector<int>& v) {
  if (root == nullptr) {
    return;
  }

  binary_tree_to_vector_rec(root->left, v);
  v.push_back(root->data);
  binary_tree_to_vector_rec(root->right, v);
}

vector<int> binary_tree_to_vector(BinaryTreeNode* root) {
  vector<int> v;
  binary_tree_to_vector_rec(root, v);
  return v;
}

void display_level_order(BinaryTreeNode* root) {
  if (root == nullptr) {
    return;
  }

  queue<BinaryTreeNode*> q;
  q.push(root);
  q.push(nullptr);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();
    cout << temp->data << ", ";
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }

    if (q.front() == nullptr) {
      cout << endl;
      q.pop();
      if (!q.empty()) {
        q.push(nullptr);
      }
    }

  }
  cout << endl;
}
string display_BT(BinaryTreeNode* root) {
  string result = "";
  if (root == nullptr) {
    return "";
  }

  queue<BinaryTreeNode*> q;
  q.push(root);
  q.push(nullptr);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();
    result += std::to_string(temp->data) +", ";
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }

    if (q.front() == nullptr) {
      q.pop();
      if (!q.empty()) {
        q.push(nullptr);
      }
    }

  }
  return result;
}

void get_level_order(BinaryTreeNode* root, vector<int>& output) {
  if (root == nullptr) {
    return;
  }

  queue<BinaryTreeNode*> q;
  q.push(root);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();

    output.push_back(temp->data);
    
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }
  }
}

void another_display_tree(BinaryTreeNode* root, int tabs) {
  if (root != nullptr) {
    int i;

    if (root->left != nullptr) {
      for(i = 0; i < tabs+4; ++i) {
        cout << ' ';
      }
      cout << "L" << root->left->data << endl;
    }

    if (root->right != nullptr) {
      for(i = 0; i < tabs+4; ++i) {
        cout << ' ';
      }
      cout << "R" << root->right->data << endl;
    }

    another_display_tree(root->left, tabs + 4);
    another_display_tree(root->right, tabs + 4);
  }
}

void another_display_tree(BinaryTreeNode* root) {
  if (root != nullptr) {
    cout << root->data << endl;
    another_display_tree(root, 0);
  }
}

bool is_identical_tree(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }
  else if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            is_identical_tree(root1->left, root2->left) &&
            is_identical_tree(root1->right, root2->right));
  }
  else {
    return false;
  }
}

void populate_parents_rec(BinaryTreeNode* root, BinaryTreeNode* parent) {
  if (root == nullptr) {
    return;
  }

  root->parent = parent;

  populate_parents_rec(root->left, root);
  populate_parents_rec(root->right, root);
}

void populate_parents(BinaryTreeNode* root) {
  populate_parents_rec(root, nullptr);
}

bool are_identical_trees(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }
  
  if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            are_identical_trees(root1->left, root2->left) &&
            are_identical_trees(root1->right, root2->right));
  }

  return false;
}

void print(vector<int>& v) {
  cout << "vector = {";
  for (int x : v) {
    cout << x << ",";
  }
  cout << "}" << endl;
}

template <class T>
void print_list(vector<T>& v) {
  cout << "{ ";
  for (auto x : v) {
    cout << x << ",";
  }
  cout << "}" << endl;
}

template <class T>
bool is_equal(vector<T>& v1, vector<T>& v2) {
  if (v1.size() != v2.size()) {
    return false;
  }

  int idx = 0;
  for (auto x : v1) {
    if (x != v2[idx]) {
      return false;
    }
    ++idx;
  }

  return true;
}

template<typename T>
vector<T> create_random_vector(int length, T max_value = 100) {
  vector<T> v(length);
  srand (time(nullptr));
  for(T i = 0; i < length; ++i) {
    v[i] = static_cast<T>(rand() % max_value);
  }
  return v;
}

vector<int> create_random_vector(int length, int max_value = 100) {
  vector<int> v(length);
  srand (time(nullptr));
  for(int i = 0; i < length; ++i) {
    v[i] = rand() % max_value;
  }
  return v;
}

int find_in_vector(vector<int>& v, int k) {
  for (int i = 0; i < v.size(); ++i) {
    if (k == v[i]) {
      return i;
    }
  }
  return -1;
}

bool is_sorted(vector<int> v) {

  for (int i = 1; i < v.size(); ++i) {
    if (v[i] < v[i-1]) {
      return false;
    }
  }

  return true;
}

void level_order_using_next(BinaryTreeNode* root) {
  while (root != nullptr) {
    cout << root->data << ",";
    root = root->next;
  }
  cout << endl;
}

class connectSiblings{
    public static void populate_sibling_pointers(BinaryTreeNode root) {
    //TODO: Write - Your - Code
  }
} 

import java.util.*;
import java.io.*;
import java.math.*;

class BinaryTreeNode
{
    public int data;
    public BinaryTreeNode left;
    public BinaryTreeNode right;

    // below data members used only for some of the problems
    public BinaryTreeNode next;
    public BinaryTreeNode parent;
    public int count;

    public BinaryTreeNode(int d) {
      data = d;
      left = null;
      right = null;
      parent = null;
      count = 0;
    }
}
class BinaryTree {

public static BinaryTreeNode root;

public BinaryTree() {
  root = null;
}
 public static List<Integer> get_level_order_traversal_with_sibling(BinaryTreeNode root)
  {
    List<Integer> l = new ArrayList<Integer>();
    while(root != null) {
      l.add(root.data);
      // System.out.print(root.data + ", ");
      root = root.next;
    }
    return l;
  }
  
public BinaryTree(BinaryTreeNode head) {
  this.root = head;
}

public static BinaryTreeNode insert(BinaryTreeNode root, int d) {

  BinaryTreeNode pNew = new BinaryTreeNode(d);
  if (root == null) {
    return pNew;
  }

  BinaryTreeNode parent = null;
  BinaryTreeNode pTemp = root;
  while (pTemp != null) {
    parent = pTemp;
    if (d <= pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }

  if (d <= parent.data) {
    parent.left = pNew;
    pNew.parent = parent;
  } else {
    parent.right = pNew;
    pNew.parent = parent;
  }  
  return root;
}

public static BinaryTreeNode insert_BT(BinaryTreeNode root, int d) {

  BinaryTreeNode pNew = new BinaryTreeNode(d);
  if (root == null) {
    return pNew;
  }

  BinaryTreeNode parent = null;
  BinaryTreeNode pTemp = root;
  while (pTemp != null) {
    parent = pTemp;
    if (d <= pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }

  Random generator = new Random();
  int dir = generator.nextInt(1000);

  if (dir%2 == 0) {
    parent.left = pNew;
    pNew.parent = parent;
  } else {
    parent.right = pNew;
    pNew.parent = parent;
  }  
  return root;
}

public static BinaryTreeNode find_in_bst(BinaryTreeNode root, int d){
  if(root == null)
    return null;

  if(root.data == d) {
    return root;
  }
  else if(root.data > d){
    return find_in_bst(root.left,d);
  }
  else{
    return find_in_bst(root.right,d);
  }
}


public static void display_inorder(BinaryTreeNode node) {
  if (node == null) {
    return;
  }
  display_inorder(node.left);
  if(node.parent != null)
  {
    //System.out.print(String.format("[%d - %d]",node.parent.data, node.count));
  }
  System.out.print(node.data + ", ");
  display_inorder(node.right);
}

public static void get_inorder(BinaryTreeNode node, List<Integer> output) {
  if (node == null) {
    return;
  }
  get_inorder(node.left, output);
  output.add(node.data);
  get_inorder(node.right, output);
}

public static void get_preorder(BinaryTreeNode node, List<Integer> output) {
  if (node == null) {
    return;
  }
  output.add(node.data);
  get_preorder(node.left, output);
  get_preorder(node.right, output);
}

public static BinaryTreeNode create_BST(List<Integer> l) {
  BinaryTreeNode root = null;
  for (Integer x : l) {
    root = insert(root, x);
  }
  return root;
}

public static BinaryTreeNode create_random_BST(int count, int max_value) {
  BinaryTreeNode root = null;
  for (int i = 0; i < count; ++i) {
    Random generator = new Random();
    root = insert(root, generator.nextInt(max_value));
  }
  return root;
}

public static BinaryTreeNode create_random_BST(int count) {
  return create_random_BST(count, Integer.MAX_VALUE);
}

public static BinaryTreeNode create_binary_tree(int count) {
  BinaryTreeNode root = null;
  for (int i = 0; i < count; ++i) {
    Random generator = new Random();
    root = insert_BT(root, generator.nextInt(100));
  }
  return root;
}

private static void populate_parents_rec(BinaryTreeNode root, BinaryTreeNode parent) {
  if (root == null) {
    return;
  }

  root.parent = parent;

  populate_parents_rec(root.left, root);
  populate_parents_rec(root.right, root);
}

public static void populate_parents(BinaryTreeNode root) {
  populate_parents_rec(root, null);
}

public static void bst_to_arraylist_rec(BinaryTreeNode root, ArrayList<Integer> arr) {
  if (root == null) {
    return;
  }

  bst_to_arraylist_rec(root.left, arr);
  arr.add(root.data);
  bst_to_arraylist_rec(root.right, arr);
}

public static ArrayList<Integer> bst_to_arraylist(BinaryTreeNode root) {
  ArrayList<Integer> arr = new ArrayList<Integer>();
  bst_to_arraylist_rec(root, arr);
  return arr;
}

public static void another_display_tree(BinaryTreeNode root, int tabs) {
  if (root != null) {
    int i;

    if (root.left != null) {
      for(i = 0; i < tabs+4; ++i) {
        System.out.print(" ");
      }
      System.out.print("L" + root.left.data + "\n");
    }

    if (root.right != null) {
      for(i = 0; i < tabs+4; ++i) {
        System.out.print(" ");
      }
      System.out.print("R" + root.right.data + "\n");
    }

    another_display_tree(root.left, tabs + 4);
    another_display_tree(root.right, tabs + 4);
  }
}

public static void another_display_tree(BinaryTreeNode root) {
  if (root != null) {
    System.out.print(root.data + "\n");
    another_display_tree(root, 0);
  }
}

public static void display_level_order(BinaryTreeNode root) {
  if(root == null)
    return;

  ArrayDeque<BinaryTreeNode> queue = new ArrayDeque<BinaryTreeNode>();
  queue.addLast(root);

  while(!queue.isEmpty()){
    BinaryTreeNode temp = queue.removeFirst();
    System.out.print(temp.data + ", ");

    if(temp.left != null) {
      queue.addLast(temp.left);
      //System.out.println(temp.left.data + "LEFT");
    }

    if(temp.right != null){
      queue.addLast(temp.right);
      //System.out.println(temp.right.data + "RIGHT");
    }
  }
    System.out.println();
}

public static List<Integer> get_level_order(BinaryTreeNode root) {

  List<Integer> output = new ArrayList<Integer>();

  if(root == null)
    return output;

  ArrayDeque<BinaryTreeNode> queue = new ArrayDeque<BinaryTreeNode>();
  queue.addLast(root);

  while(!queue.isEmpty()){
    BinaryTreeNode temp = queue.removeFirst();
    // System.out.print(temp.data + ", ");
    output.add(temp.data);

    if(temp.left != null) {
      queue.addLast(temp.left);
      //System.out.println(temp.left.data + "LEFT");
    }

    if(temp.right != null){
      queue.addLast(temp.right);
      //System.out.println(temp.right.data + "RIGHT");
    }
  }
  return output;
}

public static boolean is_identical_tree(BinaryTreeNode root1, BinaryTreeNode root2) {
  if (root1 == null && root2 == null) {
    return true;
  }
  else if (root1 != null && root2 != null) {
    return ((root1.data == root2.data) &&
            is_identical_tree(root1.left, root2.left) &&
            is_identical_tree(root1.right, root2.right));
  }
  else {
    return false;
  }
}
}


class ListUtil{
  public static <T> boolean is_equal(List<T> v1, List<T> v2) {
    if(v1.size() != v2.size()){
      return false;
    }

    for(int i= 0 ; i < v1.size() ; i++) {
      if(!v1.get(i).equals(v2.get(i))) {
        System.out.println(v1.get(i) + "not equal" + v2.get(i));
        return false;
      }
    }

    return true;
  }

  /*public static boolean is_equal(List<Integer> v1, List<Integer> v2) {
    if(v1.size() != v2.size()){
      return false;
    }
    for(int i= 0 ; i < v1.size() && i < v2.size(); i++) {
      //System.out.print(String.format("\n%d-%d\n", v1.get(i),v1.get(i)));
      if(v1.get(i) - v2.get(i) != 0) {
        return false;
      }
    }
    System.out.print(String.format("\nTRUE\n"));
    return true;
  }*/

  public static void print(List<Integer> l) {
    for (Integer i : l) {
      System.out.print(i + ", ");
    }
    System.out.println();
  }

  public static ArrayList<Integer> createRandomList(int length) {
    ArrayList<Integer> l = new ArrayList<Integer>();
    for (int i = 1; i < length + 1; ++i) {
      l.add(i);
    }

    Collections.shuffle(l);
    return l;
  }

  public static List<Integer> create_random_list(int length, int max_value) {
    List<Integer> l = new ArrayList<Integer>();
    for (int i = 1; i < length + 1; ++i) {
      l.add(new Random().nextInt(max_value));
    }

    Collections.shuffle(l);
    return l;
  }
}

Java

def populate_sibling_pointers(root):
  #TODO: Write - Your - Code
  return root

import os, sys, io, pickle
utils_path = os.path.join('..', '..', '..', '..', 'problems', 'utils', 'python')
sys.path.append(utils_path)

from collections import deque

def print_list(v):
  for i in range(0,len(v)):
    print(str(v[i]), end = " ")
  print("")

def are_lists_equal(v1, v2):
  if len(v1) != len(v2):
    return False

  for n1, n2 in zip(v1, v2):
    if n1 != n2:
      return False

  return True

def create_random_list(count):
  output = []
  for i in range(0, count):
    output.append(random.randrange(1, sys.maxint))
  return output


class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
    self.next = None
    self.parent = None


import random

def insert_binary_tree(root, d):
  pNew = BinaryTreeNode(d)
  if root == None:
    return pNew

  parent = None
  pTemp = root
  while (pTemp != None): 
    parent = pTemp
    if d < pTemp.data:
      pTemp = pTemp.left
    else:
      pTemp = pTemp.right

  if d <= parent.data:
    parent.right = pNew
  else:
    parent.left = pNew

  return root

def insert(root, d):
  pNew = BinaryTreeNode(d)
  if root == None:
    return pNew

  parent = None
  pTemp = root
  while (pTemp != None): 
    parent = pTemp
    if d < pTemp.data:
      pTemp = pTemp.left
    else:
      pTemp = pTemp.right

  if d < parent.data:
    parent.left = pNew
  else:
    parent.right = pNew

  return root

def find_in_bst(root, d):
  if root == None:
    return None

  if root.data == d:
    return root
  elif root.data > d:
    return find_in_bst(root.left, d)
  else:
    return find_in_bst(root.right, d)

# find node in inorder 
# works for both BST and binary tree
def find_node(root, d):
  if root == None:
    return

  if root.data == d:
    return root

  temp = find_node(root.left, d)
  if temp != None:
    return temp

  return find_node(root.right, d) 

def display_inorder(node):
  if node == None:
    return

  display_inorder(node.left)
  print(str(node.data), end = ", ")
  display_inorder(node.right)

def create_BST(arr):
  root = None
  for x in arr:
    root = insert(root, x)
  return root

def create_binary_tree(count):
  root = None
  for i in range(1, count):
    root = insert_binary_tree(root, random.randrange(1,100))
  return root

def create_random_BST(count):
  root = None;
  for i in range(1, count):
    root = insert(root, random.randrange(200, 300))
  return root

def bst_to_list_rec(root, lst):
  if root == None:
    return

  bst_to_list_rec(root.left, lst)
  lst.append(root.data)
  bst_to_list_rec(root.right, lst)

def bst_to_list(root):
  lst = []
  bst_to_list_rec(root, lst)
  return lst

def insert_at_head(head, data):
  newNode = LinkedListNode(data)
  newNode.next = head
  return newNode

def populate_parents_rec(root, parent):
  if root == None:
    return 
  root.parent = parent

  populate_parents_rec(root.left, root)
  populate_parents_rec(root.right, root)

def populate_parents(root):
  populate_parents_rec(root, None)

def display_level_order(root):
  if root == None:
    return
  q = deque()
  q.append(root)

  while q:
    temp = q.popleft()
    print(str(temp.data), end = ",")
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)

  print

def get_level_order(root):
  output = []
  if root == None:
    return output
  
  q = deque()
  q.append(root)

  while q:
    temp = q.popleft()
    output.append(temp.data)
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)

  return output

def get_inorder_helper(root, output):
  if root == None:
    return output

  output = get_inorder_helper(root.left, output)
  output.append(root.data)
  output = get_inorder_helper(root.right, output)
  
  return output

def get_inorder(root):
  output = []
  return get_inorder_helper(root, output)

def is_identical_tree(root1,root2):
  if root1 == None and root2 == None:
    return True

  if root1 != None and root2 != None and root1.data == root2.data: 
    return is_identical_tree(root1.left,root2.left) and is_identical_tree(root1.right,root2.right)

  return False

Python

let populate_sibling_pointers = function(root) {
   //TODO: Write - Your - Code
  return root;
};

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  display_level_order() {
    if (!this) {
      return;
    }
    let q = [];
    q.push(this);

    while (q.length > 0) {
      let temp = q.shift();
      console.log(temp.data + ",");

      for (let c in temp.children) {
        q.push(temp.children[c]);
      }
    }
  }
}

class BinaryTreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.next = null;
    this.parent = null;
  }
}

class LinkedListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
    this.arbitrary = null;
  }
}

let insert_binary_tree = function(root, d) {
  let pNew = new BinaryTreeNode(d);
  if (!root) {
    return pNew;
  }

  let parent = null;
  let pTemp = root
  while (pTemp) {
    let parent = pTemp;
    if (d < pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }
  if (d <= parent.data) {
    parent.right = pNew;
  } else {
    parent.left = pNew;
  }

  return root;
}

let insert = function(root, d) {
  let pNew = new BinaryTreeNode(d);
  if (!root) {
    return pNew;
  }

  let parent = null;
  let pTemp = root;
  while (pTemp) {
    parent = pTemp;
    if (d < pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }
  if (d < parent.data) {
    parent.left = pNew;
  } else {
    parent.right = pNew;
  }

  return root;
}

let find_in_bst = function(root, d) {
  if (!root) {
    return null;
  }

  if (root.data === d) {
    return root;
  } else if (root.data > d) {
    return find_in_bst(root.left, d);
  } else {
    return find_in_bst(root.right, d);
  }
}
// find node in inorder 
// works for both BST and binary tree
let find_node = function(root, d) {
  if (!root) {
    return;
  }

  if (root.data === d) {
    return root;
  }

  let temp = find_node(root.left, d);
  if (temp) {
    return temp;
  }

  return find_node(root.right, d);
}

let display_inorder = function(node) {
  if (!node) {
    return;
  }

  display_inorder(node.left);
  console.log(node.data + ", ");
  display_inorder(node.right);
}
let create_BST = function(arr) {
  let root = null;
  for (let x in arr) {
    root = insert(root, arr[x]);
  }
  return root;
}

let create_binary_tree = function(count) {
  let root = null;
  for (let i = 1; i < count; i++) {
    root = insert_binary_tree(root, Math.floor(Math.random() * 100 + 1));
  }
  return root;
}

let create_random_BST = function(count) {
  let root = null;
  for (let i = 1; i < count; i++) {
    root = insert(root, Math.floor(Math.random() * 100 + 200));
  }
  return root;
}

let bst_to_list_rec = function(root, lst) {
  if (!root) {
    return;
  }

  bst_to_list_rec(root.left, lst);
  lst.push(root.data);
  bst_to_list_rec(root.right, lst);
}

let bst_to_list = function(root) {
  let lst = [];
  bst_to_list_rec(root, lst);
  return lst;
}

let populate_parents_rec = function(root, parent) {
  if (!root) {
    return;
  }
  root.parent = parent;

  populate_parents_rec(root.left, root);
  populate_parents_rec(root.right, root);
}

let populate_parents = function(root) {
  populate_parents_rec(root, null);
}

let display_level_order = function(root) {
  if (!root) {
    return;
  }
  let q = [];
  q.push(root);
  let print_level = '';
  while (q.length > 0) {
    let temp = q.shift();
    print_level += temp.data + ",";
    if (temp.left) {
      q.push(temp.left);
    }
    if (temp.right) {
      q.push(temp.right)
    }
  }
  console.log(print_level);
}

let get_level_order = function(root) {
  let output = [];
  if (!root) {
    return output;
  }

  let q = [];
  q.push(root);

  while (q.length > 0) {
    let temp = q.shift();
    output.push(temp.data);
    if (temp.left) {
      q.push(temp.left);
    }
    if (temp.right) {
      q.push(temp.right);
    }
  }
  return output;
}

let get_inorder_helper = function(root, output) {
  if (!root) {
    return output;
  }

  output = get_inorder_helper(root.left, output);
  output.push(root.data);
  output = get_inorder_helper(root.right, output);

  return output;
}

let get_inorder = function(root) {
  let output = [];
  return get_inorder_helper(root, output);
}

let is_identical_tree = function(root1, root2) {
  if (!root1 && !root2) {
    return true;
  }

  if (root1 && root2 && root1.data === root2.data) {
    return is_identical_tree(root1.left, root2.left) && is_identical_tree(root1.right, root2.right);
  }

  return false;
}

JavaScript

def populate_sibling_pointers(root)
  #TODO: Write - Your - Code
 return root
end

class BinaryTreeNode
  attr_accessor :data, :left, :right, :next, :parent, :count
  def initialize(data)
    @data = data
    @left = nil
    @right = nil
    @next = nil
    @parent = nil
    @count = -1
  end
end

def insert_binary_tree(root, d)
  pNew = BinaryTreeNode.new(d)
  if (!root)
    return pNew
  end

  parent = nil
  pTemp = root
  while (pTemp)
    parent = pTemp
    if (d < pTemp.data)
      pTemp = pTemp.left
    else
      pTemp = pTemp.right
    end
  end
  if (d <= parent.data)
    parent.right = pNew
  else
    parent.left = pNew
  end

  return root
end

def insert(root, d)
  pNew = BinaryTreeNode.new(d)
  if (!root)
    return pNew
  end

  parent = nil
  pTemp = root
  while (pTemp)
    parent = pTemp
    if (d < pTemp.data)
      pTemp = pTemp.left
    else
      pTemp = pTemp.right
    end
  end
  if (d < parent.data)
    parent.left = pNew
  else
    parent.right = pNew
  end

  return root
end

def find_in_bst(root, d)
  if (!root)
    return nil
  end

  if (root.data == d)
    return root
  elsif (root.data > d)
    return find_in_bst(root.left, d)
  else
    return find_in_bst(root.right, d)
  end
end

# find node in inorder
# works for both BST and binary tree
def find_node(root, d)
  if (!root)
    return
  end

  if (root.data == d)
    return root
  end

  temp = find_node(root.left, d)
  if (temp)
    return temp
  end

  return find_node(root.right, d)
end

def display_inorder(node)
  if (!node)
    return
  end

  display_inorder(node.left)
  print (node.data.to_s + ", ")
  display_inorder(node.right)
end
def create_BST(arr)
  root = nil
  arr.each do |x|
    root = insert(root, x)
  end
  return root
end

def create_binary_tree(count)
  root = nil
  (count-1).times do |i|
    root = insert_binary_tree(root, (rand * 100 + 1).floor)
  end
  return root
end

def create_random_BST(count)
  root = nil
  (count-1).times do |i|
    root = insert(root, (rand * 100 + 200).floor)
  end
  return root
end

def bst_to_list_rec(root, lst)
  if (!root)
    return
  end

  bst_to_list_rec(root.left, lst)
  lst.push(root.data)
  bst_to_list_rec(root.right, lst)
end

def bst_to_list(root)
  lst = []
  bst_to_list_rec(root, lst)
  return lst
end

def populate_parents_rec(root, parent)
  if (!root)
    return
  end
  root.parent = parent

  populate_parents_rec(root.left, root)
  populate_parents_rec(root.right, root)
end

def populate_parents(root)
  populate_parents_rec(root, nil)
end

def display_level_order(root)
  if (!root)
    return
  end
  q = []
  q.push(root)
  print_level = ''
  while (q.length > 0)
    temp = q.shift()
    print_level += temp.data.to_s + ","
    if (temp.left)
      q.push(temp.left)
    end
    if (temp.right)
      q.push(temp.right)
    end
  end
  print (print_level)
end

def get_level_order(root)
  output = []
  if (!root)
    return output
  end

  q = []
  q.push(root)

  while (q.length > 0)
    temp = q.shift()
    output.push(temp.data)
    if (temp.left)
      q.push(temp.left)
    end
    if (temp.right)
      q.push(temp.right)
    end
  end
  return output
end

def get_inorder_helper(root, output)
  if (!root)
    return output
  end

  output = get_inorder_helper(root.left, output)
  output.push(root.data)
  output = get_inorder_helper(root.right, output)

  return output
end

def get_inorder(root)
  output = []
  return get_inorder_helper(root, output)
end

def is_identical_tree(root1, root2)
  if (!root1 && !root2)
    return true
  end

  if (root1 && root2 && root1.data == root2.data)
    return is_identical_tree(root1.left, root2.left) && is_identical_tree(root1.right, root2.right)
  end

  return false
end

Ruby

void populate_sibling_pointers(BinaryTreeNode* root) {
  if (root == nullptr) {
    return;
  }
  
  BinaryTreeNode* current = root;
  BinaryTreeNode* last = root;
  
  while (current != nullptr) {
    if (current->left != nullptr) {
      last->next = current->left;
      last = current->left;
    }
    
    if (current->right != nullptr) {
      last->next = current->right;
      last = current->right;
    }
    
    last->next = nullptr;
    current = current->next;
  }
}

void reset_siblings(BinaryTreeNode* root) {
  if (root == nullptr) return;
  root->next = nullptr;
  reset_siblings(root->left);
  reset_siblings(root->right);
}

int main(int argc, char* argv[]) {
  
  BinaryTreeNode* root = create_random_BST(15);
  display_level_order(root);
  cout << endl << "level_order_using_next";
  level_order_using_next(root);
  
  cout << endl;
  reset_siblings(root);
  populate_sibling_pointers(root);
  level_order_using_next(root);
}

class connectSiblings{
  public static void populate_sibling_pointers(BinaryTreeNode root) {
    if(root == null)
      return;

    BinaryTreeNode current = root;
    BinaryTreeNode last = root;

    while(current != null) {
      if(current.left != null) {
        last.next = current.left;
        last = current.left;
      }

      if(current.right != null){
        last.next = current.right;
        last = current.right;
      }
    
      last.next = null;
      current = current.next;
    }
  }
  public static List<Integer> get_level_order_traversal_with_sibling(BinaryTreeNode root)
  {
    List<Integer> l = new ArrayList<Integer>();
    while(root != null) {
      l.add(root.data);
      // System.out.print(root.data + ", ");
      root = root.next;
    }
    return l;
  }

  public static void main(String[] args) {
    
    List<Integer> input = new ArrayList<Integer>();
    input.add(100);input.add(25);input.add(75);input.add(15);input.add(350);input.add(300);input.add(10);
    input.add(50);input.add(200);input.add(400);input.add(325);input.add(375);
    BinaryTreeNode root = BinaryTree.create_BST(input);

    BinaryTree.display_level_order(root);
    populate_sibling_pointers(root);
    
    System.out.println("Root -> next: "+ root.next.data); //25
    System.out.println("Root->right->left->next: "+ root.right.left.next.data); //400
    System.out.println("Root->right->right->next: "+ root.right.right.next.data); //10
    System.out.println("Root->right->right->left->next: "+ root.right.right.left.next); //None

    List<Integer> l1 = BinaryTree.get_level_order(root);
    List<Integer> l2 = get_level_order_traversal_with_sibling(root);
    System.out.println("Connected? = "+ Boolean.toString(ListUtil.is_equal(l1, l2)));
    System.out.println();
    ListUtil.print(l1);
  }
}  

def populate_sibling_pointers(root):
  if root == None:
    return

  current = root
  last = root

  while current != None:
    if current.left != None:
      last.next = current.left
      last = current.left

    if current.right != None:
      last.next = current.right
      last = current.right

    last.next = None  
    current = current.next
    
def level_order_traversal_with_sibling(root):
  while root != None:
    print(str(root.data), end = ",")
    root = root.next

def main():
  v = [100,25,75,15,350,300,10,50,200,400,325,375]
  root = create_BST(v)
  display_level_order(root)
  populate_sibling_pointers(root)
  
  print(root.next.data)#25
  print(root.right.left.next.data) #400
  print(root.right.right.next.data) #10
  print(root.right.right.left.next) #None

main()    

def populate_sibling_pointers_1(root)
  if (!root)
    return
  end

  current = root
  last = root

  while (current)
    if (current.left)
      last.next = current.left
      last = current.left
    end
    if (current.right)
      last.next = current.right
      last = current.right
    end
    last.next = nil
    current = current.next
  end
end

def main()
  v = [100,25,75,15,350,300,10,50,200,400,325,375]
  root = create_BST(v)
  display_level_order(root)
  populate_sibling_pointers_1(root)  
  puts root.next.data #25
  puts root.right.left.next.data #400
  puts root.right.right.next.data #10
  if root.right.right.left.next == nil
    puts  "Nil"
  end
end

main

# Solution Explanation
## Runtime Complexity
Linear, O(n).

## Memory Complexity
Constant O(1).

<br>

## Solution Breakdown

A binary tree is a data structure made up of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root. Every node except the 'root' node is connected by a directed edge from exactly one other node. This node is called the parent of that node. On the other hand, each node can be connected to an arbitrary number of nodes, called children. Nodes with the same parent node are called siblings.

Each node in the above binary tree has one more pointer i.e. next along with the left and right  pointers. 'Next' is used to connect one node to the other. After connecting siblings, a linked-list-like structure is formed whose head is the root node. We keep two pointers current and last. 'current' is the node we are working at and 'last' is the last node in the linked list already constructed (i.e. siblings already connected). Below are the steps we use to connect all siblings in the tree:

```xml
Initially set both current and last as 'root'
while current node is not null
  If current node has a left child, append this left node to the last and make it last node.
  If current node has a right child, append this right node to the last and make it last node.
  update current node to current's next node
```



> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Given the root to a binary tree where each node has an additional pointer called a sibling (or next), connect the sibling pointer to the next node in the same level. The last node in each level should point to the first node of the next level in the tree.

Connect All Siblings

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown