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); }