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<treenode*> 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;i<sz;i++) {   extract front node of the queue  treenode *currentnode="Q.front();"  q.pop();  if(prev !="NULL){" if this is not first in level, make it next_right previous one  prev->next_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 --------
</sz;i++)></treenode*>

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 --------