Populating Next Right Pointers in Each Node in a Binary Tree

Populating Next Right Pointers in Each Node if the given tree is a binary tree? 

For example,

Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Solution:

 public void connect(TreeLinkNode root) {

        Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();

        

        if(root==null)

            return;

        queue.add(root);

        // add null to remember level

        queue.add(null);

        while(!queue.isEmpty()) {

            TreeLinkNode temp = queue.poll();

            if(temp!=null) {

                temp.next = queue.peek();

                if(temp.left!=null) {

                    queue.add(temp.left);

                }

                if(temp.right!=null) {

                    queue.add(temp.right);

                }

            }

            // if queue is not empty, push NULL to mark nodes at this level are visited

            else if(!queue.isEmpty()) {

                queue.add(null);

            }

            

        }

    }

Populate next right pointers in each node of full binary tree

Problem:
Given a binary tree

class BTNode {
BTNode left;
BTNode right;
BTNode nextRight;
}
Populate the nextRight pointers in each node.

You may assume that it is a full binary tree (ie, each node other than the leaves has two children.)

Approach:
The trick is to re-use the populated nextRight pointers. Before we pass the left and right to the recursion function itself, we connect the rightChild’s nextRight to the current node’s nextRight’s leftChild. In order for this to work, the current node’s nextRight pointer must be populated, which is true in this case.

1 2 3 4 5 6 7 8 9 10

void connect(Node* p) {   if (p == null) return;   if (p.left != null)      p.left.nextRight = p.right;   if (p.right != null)     p.right.nextRight = (p.nextRight!=NULL) ?                                p.nextRight.left : NULL;   connect(p.left);   connect(p.right); }