# Populate Sibling Pointers Problem

Given a binary tree, populate next_right pointers in each node and return the root of the tree.

Definition of next_right node: If we store all the nodes of the same level in an array maintaining the same sequence as in the input tree then (i+1)th node is the next_right node of ith node.

In normal binary tree we have left_ptr and right_ptr but for this question our binary tree node structure will have next_right along with left_ptr and right_ptr which will be null initially and you are supposed to populate that based on the above mentioned definition.

Example

Input:

Output:

There are three levels in the input tree. If we write the node values level wise then we get:

Level 1: 100

Level 2: 200, 300

Level 3: 400, 500, 600, 700

In the first level there is only one node. So, next right of node having value 1 is null.

In the second level, there are 2 nodes. Left most node’s next right pointer is the rightmost node.

In the third level, there are 4 nodes. Second node is next right of first node, third node is next right to second node and fourth node is next right of third node.

#### Notes

Input Parameters: There is only one argument named root denoting the root of the input tree.

Output: Return the root of the tree after populating next_right pointers.

Constraints:

•   0 <= number of nodes <= 100000

•   0 <= values stored in the nodes <= 10^9

### Solutions

We have provided two solutions for this problem. Both are optimal considering time and memory complexity.

### 1. optimal_solution.cpp

In this solution we have followed BFS or level wise traversal approach to populate the next right pointer. I am describing the process step by step below.

• Consider root node is at level 0
• For each level i insert all the nodes of this level in a queue. As root node is in level 0, insert it into a queue
• Iterate over all the available nodes of the current level. Second node becomes the next_right of first node, third node becomes the next_right of second node and so on.
• At the same time store the left and right child of current level as nodes of the next level.
• Repeat step 3 and 4 until the queue is empty.

Time Complexity:

O(n) where n denotes the number of nodes in the tree.

As we have to traverse all the nodes of a tree, hence the time complexity is O(n).

Auxiliary Space:

O(n) where n is the number of nodes in the input tree.

As we are using a queue to store the nodes of the tree, hence O(n) extra space is required.

Space Complexity:

O(n) where n is the number of nodes in the input tree.

As to store given linked list it will take O(n) space and auxiliary

space is O(n) hence space complexity is O(n) + O(n) → O(n)

``````
// -------- START --------

/*
* Complete the function below.
*/

TreeNode* populateSiblingPointers(TreeNode* root) {
// base case
if(root == NULL){
return root;
}
// queue to store the unassigned nodes
queue Q;
// push root node in the queue
Q.push(root);
// iterate until all nodes are assigned
while(!Q.empty()){
// previous node of current level is null
TreeNode *prev = NULL;
// number of nodes in current level
int sz = Q.size();
// iterate through all the nodes of current level
for(int i=0;inext_right = currentNode;
}
if(currentNode->left_ptr){
// push left child of current node if not null
Q.push(currentNode->left_ptr);
}
if(currentNode->right_ptr){
// push right child of current node if not null
Q.push(currentNode->right_ptr);
}
// make current node as previous node
prev = currentNode;

}
}
return root;
}

// -------- END --------
``````

### 2. other_solution.cpp

In this solution we have followed DFS traversal approach to populate the next right pointer. Left child’s next_right pointer is the right child or next available child of any parent which is situated at the right side of the parent. Right child’s next_right pointer is next available child of any parent which are situated at the right side of the parent

Time Complexity:

O(n) where n denotes the number of nodes in the tree.

As we have to traverse all the nodes of a tree, hence the time complexity is O(n).

Auxiliary Space:

O(n) where n is the number of nodes in the input tree for using recursion which implicitly use a stack.

Space Complexity:

O(n) where n is the number of nodes in the input tree.

As to store given linked list it will take O(n) space and auxiliary

space is O(n) hence space complexity is O(n) + O(n) → O(n)

``````
// -------- START --------

TreeNode *getNextRightUsingNextRightOfParent(TreeNode *node){
TreeNode *next_right = node;
// while next right is not null
while (next_right) {
if(next_right->left_ptr){
// if current node has left child, return this child
return next_right->left_ptr;
} else if (next_right->right_ptr) {
// if current node has right child, return this child
return next_right->right_ptr;
}
// otherwise go the the next right of current node
next_right = next_right->next_right;
}
return NULL;
}

void populateSiblingPointersHelper(TreeNode *root){
// base case. If current node is null, return
if(root == NULL){
return;
}

if(root->left_ptr){
// if current node has a left child
if(root->right_ptr){
// If current node has a right child, then this will be the next roight node of left child
root->left_ptr->next_right = root->right_ptr;
} else {
// otherwise iterate over next right pointer of parents to find out next available node
root->left_ptr->next_right = getNextRightUsingNextRightOfParent(root->next_right);
}
}
if(root->right_ptr){
// iterate over next right pointer of parents to find out next available node
root->right_ptr->next_right = getNextRightUsingNextRightOfParent(root->next_right);
}

populateSiblingPointersHelper(root->right_ptr);
populateSiblingPointersHelper(root->left_ptr);
}

/*
* Complete the function below.
*/
TreeNode* populateSiblingPointers(TreeNode* root){
// base case
if(root == NULL){
return root;
}
// invoke the helper method
populateSiblingPointersHelper(root);
return root;
}

// -------- END --------
``````

All Posts