A binary tree problem – Populating next right pointers in each node
March 12, 2010 in binary tree
Given a binary tree
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.)
The solution is not immediately obvious to me at first. However, with some help of diagrams, there are some observations can be made.
- Most likely this can be implemented recursively, because you can identify the linking of nodes as sub-problems.
- The main difficulty of this problem is linking rightChild with the nextSibling of rightChild.
- Each node has no parent pointer. Therefore, there is no way linking the rightChild with its nextSibling at a level.
My first thought is to use Breadth-First Search (BFS). After all, we are connecting the nextRight node level-by-level, it is only natural to apply BFS to this problem. I mentioned this approach to the interviewer, but he was not too satisfied with it.
BFS requires memory space to store Nodes into a queue. Can we do better without extra space?
To do that, we need to first solve the 3 problems mentioned above. We know this problem requires a recursive solution, and most people will start with something like: “Connect the current node to its sibling, then pass the leftChild to itself, and then the rightChild to itself. Stop recursion when node is NULL.” This will not work. You are only connecting the leftChild with the rightChild. How about the rightChild? The next pointer of rightChild still do not point to anywhere! (EDIT: This method will work with one small modification, see below)
The first key to solving this problem is we have the nextRight pointer. Assume that the nextRight pointers are already populated for this level. How can we populate the next level? Easy… just populate by iterating all nodes on this level. Another key to this problem is you have to populate the next level before you go down to the next level, because once you go down, you have no parent pointer, and you would have hard time populating, as I mentioned in the observation I made earlier.
With the problem sorted out, we can implement this in code in a pretty straight-forward manner. (But beware of checking for NULL de-referencing pointers!)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void connect(Node* p) { if (p == NULL) return; if (p->leftChild == NULL || p->rightChild == NULL) return; Node* rightSibling; Node* p1 = p; while (p1) { if (p1->nextRight) rightSibling = p1->nextRight->leftChild; else rightSibling = NULL; p1->leftChild->nextRight = p1->rightChild; p1->rightChild->nextRight = rightSibling; p1 = p1->nextRight; } connect(p->leftChild); } |
EDIT: (Added alternative solution)
Here is a more elegant solution. The trick is to re-use the populated nextRight pointers. As mentioned earlier, we just need one more step for it to work. Before we passed the leftChild and rightChild 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. Why? Try to draw a series of diagram how the recursion deepens, you will immediately see that it is doing DFS (Depth first search).
1 2 3 4 5 6 7 8 9 10 11 | void connect(Node* p) { if (!p) return; if (p->leftChild) p->leftChild->nextRight = p->rightChild; if (p->rightChild) p->rightChild->nextRight = (p->nextRight) ? p->nextRight->leftChild : NULL; connect(p->leftChild); connect(p->rightChild); } |
Ming said on October 5, 2010
How about not a full tree?
void populateNextRight(NODE* node)
{
if(node == NULL) return;
int bFirstNode = 0;
NODE* nextFirstNode;
while(node)
{
if(node->left)
{
nextSibling = getNextSibling(node, 0); //starting from the right chhild of the current node.
node->left>nextRight = nextSibling;
if(bFirstNode == 0) //to find the first node in the next level
{
nextFirstNode = node->left;
bFirstNode++;
}
}
if(node->right)
{
nextSibling = getNextSibling(node->nextRight, 1); //starting from the left child of the next right
node->right>nextRight = nextSibling;
if(bFirstNode == 0)
{
nextFirstNode = node->right;
bFirstNode++;
}
}
if(!nextSibling) break; //this means no siblings in the next level.
node = node->nextRight;
}
if(nextFirstRight) populateNextRight(nextFirstNode);
else return; //which means the current level is the last level of the tree.
}
NODE* getNextSibling(NODE* curNode, int isLeft)
{
if(curNode == NULL) return NULL;
if(isLeft == 1)
{
if(curNode->left) return curNode->left;
else if(curNode->right) return curNode->right;
}
curNode = curNode->nextRight;
while(curNode)
{
if(curNode->left) return curNode->left;
else if(curNode->right) return curNode->right;
curNode = curNode->nextRight;
}
return NULL;
}
1337c0d3r said on October 6, 2010
Ming, I haven't had time to verify your solution. But, as long as you have the current level's nextRight pointers populated, you can populate the next level (even the tree is not a full tree). You just loop through the current level until you find the nextRight element for all current level's children.
It turns out that it is a straight forward extension to my first solution. My second solution wouldn't work because the nextRight pointer is not fully populated before the current level.
Ming said on October 6, 2010
Yes, you are so right. Your blog is very helpful.
online.service said on November 5, 2010
Nice solution, when i saw this one at first time, i thought BFS was good enough.
Anonymous said on November 18, 2010
This is very useful! I got exactly the same interview question, ecept that the binary tree is more general than a full binary tree: each node either has 0 child or 2 children.
1337c0d3r said on November 18, 2010
In that case, the more elegant solution (the 2nd one) will not work, as it assumes a full binary tree. The first solution could be modified a little to make it work for non-full binary tree.
Anonymous said on November 23, 2010
what about the next case. The binary tree is not a full binary tree and is not balanced ?
1337c0d3r said on November 23, 2010
See the second comment above on how to solve the general case. (Assume that the next right pointer always point to its next sibling).
benli said on December 7, 2010
I've an idea to use the right-first post-order traversal, it's O(N) solution which requries O(lgN) space.
void set_next_right(struct node * root)
{
struct node * cur = root;
struct node * last = NULL;
int level = 0, i;
struct node * array[MAX_LEVEL] = {NULL};
if (cur == NULL)
return;
push(cur);
level++;
do
{
cur = top();
if (cur == NULL)
return;
if (last == NULL || last->left == cur || last->right == cur)
{
if (cur->right)
{
push(cur->right); level ++;
} else if (cur->left)
{
push(cur->left); level ++;
}
else
{
pop(); level –;
cur->next_right = array[level];
array[level] = cur;
}
} else if (last == cur->right)
{
if (cur->left)
{
push(cur->left); level ++;
} else {
pop(); level –;
cur->next_right = array[level];
array[level] = cur;
}
} else {
pop(); level –;
cur->next_right = array[level];
array[level] = cur;
}
last = cur;
} while (1);
}
Alfred said on February 28, 2011
johny said on March 1, 2011
Hi, 1337:
I have difficulty in catching up with you here. Can’t understand why the 2nd solution of yours is only applicable to the full binary tree?
Could you elaborate more on the reason, or better, give some examples on which the 2nd solution would fail?
Thanks!
1337c0d3r said on March 1, 2011
Consider the following case that is a non-full binary tree:
Node 9′s nextRight should point to node 10. But the above algorithm would make node 9 point to NULL instead. (Becaues node 6′s leftChild’s is NULL)
Yao said on June 16, 2011
I can’t edit the previous tree of my post…And I can’t delete it …
fine, I use this example. This is a full binary tree.
(A full binary tree is a tree in which every node other than the leaves has two children(wiki)) It seems the 1st solution will return at node 4 and won’t do the node 8,9… Am I right?
jastination said on May 31, 2012
I agree with Yao’s definition of full tree, which is consistent with CLRS.
1337Coder, can you define full tree formally? Thanks,
Clive said on February 18, 2013
It looks like the first solution also fails in this example: when p1 is pointing to 5, p1->rightChild->nextRight will be p1->nextRight->leftChild, which is NULL, but it should be 10. I have a solution to fix this:
def init_right_pointers_recursive(node):
if node == None:
return
current = node
while current and current.left_child == None:
current = current.next_right
if current:
current.left_child.next_right = current.right_child
next = current.next_right
while next:
if next.left_child:
current.right_child.next_right = next.left_child
current = next
current.left_child.next_right = current.right_child
current.right_child.next_right = None
next = next.next_right
init_right_pointers_recursive(node.left_child)
Clive said on February 18, 2013
Sorry, reposting the code to reserve the indentation:
johny said on March 1, 2011
Got it, 1337.
In the scenario you provided, the 2nd solution can’t work, because when we try to determine node 9 (rightChild of node 5)’s nextRight, node 6′s nextRight hasn’t been determined yet. This is a side effect of DFS.
In contrast, the 1st solution (with some modification, like Ming’s, if node 6 doesn’t have any child, then look for its nextRight node repeatedly, until a node with child is found, to determine the rightSibling for node 9) still works.
Is my understanding correct?
johny said on March 1, 2011
Just want to add that the 1st solution still works, because nextRight is determined level by level. This is different from DFS.
1337c0d3r said on March 1, 2011
Yup, you are correct!
Just wanna add this: Essentially 1st solution is doing a BFS. It is able to do level-by-level traversal simply because there is a nextRight pointer, hence able to do BFS without using extra memory (queue).
johny said on March 1, 2011
Thanks for your confirmation, 1337. To be honest, I have checked the wiki page of BFS, and can’t understand all the queue stuff (I am not CS-backgrounded). Your solution is much clearer and simpler than the wiki page, for an example of BFS algorithm.
An off-topic question: What editor are you using to generate the neat code snippet embedded in your article? I am using UltraEdit, which doesn’t have this effect.
1337c0d3r said on March 1, 2011
You’re welcome. I used a javascript open source library called “SyntaxHighlighter” available here: http://alexgorbatchev.com/SyntaxHighlighter/
johny said on March 1, 2011
Cool tool, thanks a lot!
WgpShashank said on May 18, 2011
I think It Will Make Sense & Will Work Well Correct me if fro any test cases it will fail ??
#include
#include
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
struct node* nextRight;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->nextRight=NULL;
return(node);
}
void connect(struct node* p) {
if (!p)
return;
if (p->left)
{
if(p->right)//its necessary else NULL Pointer Exception
p->left->nextRight = p->right;
else if(p->nextRight)
{
if(p->nextRight->left)/// we can add one more if(p->nextRight)
p->left->nextRight=p->nextRight->left;
else if(p->nextRight->right)
p->left->nextRight=p->nextRight->right;
}
else
p->left->nextRight=NULL;//if all are null except that node at that level
}
if (p->right)
{
if(p->nextRight)
{
if(p->nextRight->left)//skipping checking the root null or not
p->right->nextRight =p->nextRight->left;
else if(p->nextRight->right)//skipping checking the root null or not
p->right->nextRight =p->nextRight->right;
}
else
p->right->nextRight=NULL;
}
connect(p->left);
connect(p->right);
}
/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left= newNode(6);
root->right->right= newNode(7);
root->left->left->left = newNode(8);
root->left->left->right = newNode(9);
root->left->right->left = newNode(10);
root->left->right->right = newNode(11);
root->right->left->left= newNode(12);
root->right->left->right= newNode(13);
root->right->right->left= newNode(14);
root->right->right->right= newNode(15);
connect(root);
printf( ” %d %d %d “, root->left->left->nextRight->data,root->left->right->nextRight->data,root->right->left->nextRight->data);
printf(” %d %d %d “,root->left->left->left->nextRight->data,root->left->left->right->nextRight->data,root->right->right->left->nextRight->data);//,root->right->right->right->nextRight->data); it will be null
getchar();
return 0;
}
Yao said on June 16, 2011
since A full binary tree is a tree in which every node other than the leaves has two children(wiki).
i can’t figure out the following example of the 1st solution, it seems the 1st solution won’t do 4 and 5.
Am I right?
1
/ \
2 3
/ \
4 5
Henian said on June 16, 2011
I think it may be straightforward to use the BFT method. I add a “int level” element in the tree node class. It doesn’t require the tree to be full.
template
class treeNode
{
public:
T data;
int level;
treeNode * leftChild;
treeNode * rightChild;
treeNode * nextRight;
treeNode() {};
treeNode( T data, treeNode * leftChild, treeNode * rightChild )
{
this->data = data;
this->leftChild = leftChild;
this->rightChild = rightChild;
}
};
template
void binaryTree::BFT()
{
queue< treeNode * > myqueue;
myqueue.push( root );
root->level = 0;
int currentLevel;
int preLevel = 0;
treeNode * currentNode;
while( !myqueue.empty() )
{
currentNode = myqueue.front();
myqueue.pop();
currentLevel = currentNode->level;
if( !myqueue.empty() && currentLevel == (myqueue.front())->level )
currentNode->nextRight = myqueue.front();
else
currentNode->nextRight = NULL;
if( currentLevel > preLevel )
{
cout << endl;
preLevel = currentLevel;
}
cout <data <leftChild != NULL )
{
myqueue.push( currentNode->leftChild );
(currentNode->leftChild)->level = currentNode->level + 1;
}
if( currentNode->rightChild != NULL )
{
myqueue.push( currentNode->rightChild );
(currentNode->rightChild)->level = currentNode->level + 1;
}
}
}
Sumit said on September 16, 2011
Hi, There seems to be a small Bug in your second solution. You will also need to check existence for p->rightChild while assigning p->leftChild->nextRight=p->rightChild and if it is not present then do
if(p->nextRight)
{if(p->nextRight->leftChild) assign this
else if(p->nextRight->RightChild) assign this
else assign NULL.
This should clear from a small example:
—-1—-
/ \
–2 –3–
/ / \
4– 5– 6
\ \
7 8
Let me know if i am wrong. This is for the second solution code posted above.
Sumit said on September 16, 2011
Ahh..the figure didn’t come up correctly. I’ll xplain the tree in wrds:
root = 1 ,1->left=2,1->right=3, 2->left =4, 2->right=NULL, 3->left=5,3->right=6,4->left=NULL,4->right=7,5->left=NULL,5->right=8
Sumit said on September 16, 2011
Also a while loop needs to be run for
while(p->next) and if p neither has left or right child thne check for p=p->next and assign it..
This would be clear by another example. In the above tree, instead of 5->right=8, make 6->right=8.
Sorry for 3 messages..dere’s no edit option
Ashok said on September 30, 2011
Hi Eleet(1337) coder,
I’ve just converted your idea into java version and posting here. Thanks for your original idea anyways.. It seems to be its a nice trick on BFS
public void fixNextLink(Node root) {
if(root == null) return;
// The right most child for root
Node rightmostChild = (root.right != null) ? root.right : root.left;
// Return, if there are no childs
if(rightmostChild == null) return;
// Continue to identify the sibling for root.rightmost (The right most child for root)
Node temp = root.nextPtr;
Node leftmostSibling;
while(temp != null && leftmostSibling == null){
// Left most sibling to the right in the current level from the right most node of the current node
Node leftmostSiblingInChain = (temp.left != null) ? temp.left : temp.right;
if(leftmostSiblingInChain != null) {
rightmostChild.nextPtr = leftmostSiblingInChain;
}
temp = temp.nextPtr;
}
// Finally if the left and right child exists, connect left to right
if (rightmostChild != root.left) {
root.left.nextPtr = root.right;
}
// Go down the tree to fix other links
fixNextLink(root.left);
fixNextLink(root.right);
}
Ashok said on September 30, 2011
Posting again for adding indentation
public void fixNextLink(Node root) {
….if(root == null) return;
….// The right most child for root
….Node rightmostChild = root.right != null ? root.right : root.left;
….// Return, if there are no childs
….if(rightmostChild == null) return;
….// Continue to identify the sibling for root.rightmost (The right most child for root)
….Node temp = root.nextPtr;
….Node leftmostSibling;
….while(temp != null && leftmostSibling == null){
……..// Left most sibling
……..Node leftmostSibling = temp.left != null ? temp.left : temp.right;
……..if(leftmostSibling != null) {
…………rightmostChild.nextPtr = leftmostSibling;
……..}
……..temp = temp.nextPtr;
….}
….// Finally if the left and right child exists, connect left to right
….if (rightmostChild != root.left) {
……..root.left.nextPtr = root.right;
….}
….fixNextLink(root.left);
….fixNextLink(root.right);
}
Ankur said on October 9, 2011
Working solution for general Tree(with 0 or 2 childs) ..
void PopulateNextPtr(struct node* root){
if(!root) return;
struct node* sibling = root->next;
if(!root->left && !root->right) PopulateNextPtr(sibling);
struct node* temp;
if(root->left && root->right){
root->left->next = root->right;
temp=root;
while(sibling){
if(sibling->left && sibling->right){
temp->right->next = sibling->left;
sibling->left->next = sibling->right;
temp=sibling;
}
sibling=sibling->next;
}
temp->right->next = NULL;
}
PopulateNextPtr(root->left);
}
I modified your solution a bit to achieve this..Good problem though .
maxq said on November 17, 2011
This is a good problem and thanks for the nice explanations.
I extend your method a bit to handle an arbitrary binary tree.
void connect_level(node *root)
{
if (!root)
return;
node *first=NULL, *prev=NULL;
for (node *p = root; p != NULL; p=p->nextRight) {
if (p->left) {
if (!first) first = p->left;
if (prev) prev->nextRight = p->left;
prev = p->left;
}
if (p->right) {
if (!first) first = p->right;
if (prev) prev->nextRight = p->right;
prev = p->right;
}
}
connect_level(first);
}
mohit goyal said on December 1, 2011
void connectRightMost(Node* parent, Node* left)
{
if(p->left == NULL && p->right == NULL)
return;
if(p->leftChild != NULL)
p->leftChild->nextRight = p->rightChild;
if(p->rightChild != NULL)
p->rightChild->nextRight = left;
connectRightMost(p->leftChild, p->rightChild->leftChild);
connectRightMost(p->rightChild, NULL);
}
Intially call connectRightMost(root, NULL);
jastination said on May 31, 2012
This doesn’t work. As a counter example consider a tree where left child of root is null and right child is not.
The expected result is that the nextRight pointer of root should point to the right child. I don’t see that happen in your code.
Ankur Garg said on December 7, 2011
Hello Sir,
I wrote the code which will work for any type of binary tree..Full or not full..Please go through it as I tried with few cases and it worked .
void PopulateRight(node* root){
if(!root) return;
node* temp=root->nextRight;
node* temp1=NULL;
if(root->left && root->right){
root->left->nextRight=root->right;
root->right->nextRight=NULL;
temp1=root->right;
}
else if(root->left){
root->left->nextRight=NULL;
temp1=root->left;
}
else if(root->right){
root->right->nextRight=NULL;
temp1=root->right;
}
if(temp && temp1){
if(temp->left)
temp1->nextRight=temp->left;
else if(temp->right)
temp1->nextRight=temp->right;
else
temp1->nextRight=NULL;
}
PopulateRight(root->left);
PopulateRight(root->right);
return;
}
sungjun ma said on February 16, 2012
one question, all of those method requires O(N) space.. is that different from queue based version??
Hai said on June 27, 2012
Sorry, but actually I am not quite clear what “nextRight” should be here, any explanation?
Vijay Nair said on August 7, 2012
None Recursion based solution. I consider the parent as a linked list and traverse it connecting the children. Then when the parents are all connected i move to the children as the next list of parent Nodes.
void ConnectRight ( Node *root)
{
if (!root) return;
Node *pHead = root, *cHead=null, , *cWalk=null;
pHead->next=null;
while (pHead)
{
if (pHead->left)
{
cHead == null ? { cHead=pHead->left; cWalk = pHead->left; } : { cWalk->next = pHead->left; cWalk = cWalk->next; }
}
if (pHead->right)
{
cHead == null ? { cHead=pHead->right; cWalk = pHead->right; } : { cWalk->next = pHead->right; cWalk = cWalk->right; }
}
if (cWalk) cWalk->next= null;
//pHead is guaranteed to be not null here so not checking null reference
pHead = pHead->next;
// Check if we reached end of previous level
if (!pHead)
{
pHead = cHead;
cHead = null;
cWalk = null;
}
}
}
Rakesh said on November 18, 2012
Anant Upadhyay said on December 10, 2012
The most appropriate solution is
http://www.geeksforgeeks.org/archives/16952
inheritance said on January 27, 2013
public void connect(TreeLinkNode root) {
if(root == null)
return;
root.next = null;
nextPointer(root.left, root.right);
nextPointer(root.right, null);
}
public void nextPointer(TreeLinkNode root, TreeLinkNode right){
if(root == null)
return;
root.next = right;
nextPointer(root.left, root.right);
if(right == null)
return;
nextPointer(root.right, right.left);
}
Szun said on March 30, 2013
As long as using a recursive solution, how could it possible only use constant space? One possible solution is to use an int as road mark.