Provide the Next Siblings Pointers in a Given Binary Tree

Problem

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Examples

Example 1:

Input:
          1
        /  \
       2    3
     /    /  \
    4    6    7

Output:
          1 --------> NULL
        /  \
       2 -> 3 ------> NULL
     /    /  \
    4 -> 6 -> 7 ----> NULL

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Solution

Method 1 - Using Recursion

  • Start from the root, if root’s left node is not null then make it point to the root’s right child.
  • Check if root’s nextsibling is not null,
    • if NOT then make the next sibling of root’s right node point to the root’s nextsibling’s left child. (In our example node 5 points node 6, as per our statement, Parent of node 5 is Node 2, next sibling of node 2 is node 3, and left child of node 2 is node 6, So Node 5 will points to Node 6 )
public Node connect(Node root) {
	if (root == null) return null;
	
	if (root.left != null) { // update left next
		if (root.right != null) root.left.next = root.right; // if right child exists - simple connect left.next to right
		else root.left.next = findNext(root); // if not - scan parent next node until we find the first left or right child
	}
	if (root.right != null) { // update right next
		root.right.next = findNext(root);
	}
	
	connect(root.right); // update the right nodes first
	connect(root.left);
	return root;
}

private Node findNext(Node root) { // get parent node
	while (root.next != null) { // scan all next parent nodes until we find the first left or right child
		root = root.next;
		if (root.left != null) return root.left;
		if (root.right != null) return root.right;
	}
	return null;
}

Method 2 - BFS

public Node connect(Node root) {
        if(root == null) return null;
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        
        while(!q.isEmpty()){
            int size = q.size();
            Node nextPointer = null;
            for(int i=0;i<size;i++){
                Node temp = q.poll();
                temp.next = nextPointer;
                nextPointer = temp;
                
                if(temp.right != null) {
	                q.add(temp.right);
	            }
                if(temp.left != null) {
	                q.add(temp.left);
                }
            }
        }
        return root;
    }

Method 3 - Iterative

This solution is easier to understand.

public Node connect(Node root) {
  // this head will always point to first element in current layer
  Node dummyHead  = new Node(0); 
  // this 'pre' will be the "current node" that builds every single layer     
  Node pre = dummyHead; 
  Node realRoot = root; // just for return statement
	
  while(root != null){
	  if(root.left != null){
		  pre.next = root.left;
		  pre = pre.next;
	  }
	  if(root.right != null){
		  pre.next = root.right; 
		  pre = pre.next;
	  }
	  root = root.next; 
	  // reach the end of current layer
	  
	  if(root == null){ 
	  // shift pre back to the beginning, get ready to point to the first element in next layer 
		  pre = dummyHead;  
		  //root comes down one level below to the first available non null node
		  root = dummyHead.next; ;
		  //reset dummyhead back to default null
		  dummyHead.next = null;
	  }
  }
	return realRoot;
}