A binary tree problem – Populating next right pointers in each node

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.

  1. Most likely this can be implemented recursively, because you can identify the linking of nodes as sub-problems.
  2. The main difficulty of this problem is linking rightChild with the nextSibling of rightChild.
  3. 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!)

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

VN:F [1.9.22_1171]
Rating: 4.5/5 (46 votes cast)
A binary tree problem - Populating next right pointers in each node, 4.5 out of 5 based on 46 ratings

76 thoughts on “A binary tree problem – Populating next right pointers in each node

  1. Ming

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

    VA:F [1.9.22_1171]
    +1
  2. 1337c0d3r

    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.

    VA:F [1.9.22_1171]
    0
  3. Anonymous

    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.

    VA:F [1.9.22_1171]
    0
  4. 1337c0d3r

    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.

    VA:F [1.9.22_1171]
    -1
  5. 1337c0d3r

    See the second comment above on how to solve the general case. (Assume that the next right pointer always point to its next sibling).

    VA:F [1.9.22_1171]
    +1
  6. benli

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

    VA:F [1.9.22_1171]
    +1
  7. Alfred

    VA:F [1.9.22_1171]
    +3
        1. Alex

          Hope this concise solution can help you think it through. Draw some diagrams as you walk through the code. You will understand it. BTW, the solution is for full binary trees, not general binary trees.

          VA:F [1.9.22_1171]
          0
    1. shailendra

      Actually better way to understand is this –

      This is based on BFS. BFS uses a queue which has a head and tail.
      slow is equivalent to head and tail is equivalent to tail. Because we are already connecting each node with previous node at the same level there is no need to keep a queue, just head and tail are enough.

      Rest you can figure out yourself.

      VA:F [1.9.22_1171]
      0
    2. lowiq3


      // use dummy nodes to record where should be set to null
      public static void setNextPointerBest(TreeNodeWithNext root) {
      if (root == null) return;
      TreeNodeWithNext slow = root;
      TreeNodeWithNext fast = new TreeNodeWithNext(0);
      root.next = fast;

      while (slow != fast) {
      if (slow.value != 0) { // not a dummy node
      if (slow.left != null) {
      fast.next = slow.left;
      fast = fast.next;
      }
      if (slow.right != null) {
      fast.next = slow.right;
      fast = fast.next;
      }
      } else { // dummy node
      fast.next = new TreeNodeWithNext(0);
      fast = fast.next;
      }
      slow = slow.next;
      }

      TreeNodeWithNext prev = root;
      TreeNodeWithNext curr = root.next;
      while (curr != null) {
      if (curr.value == 0) {
      prev.next = null;
      }
      prev = curr;
      curr = curr.next;
      }
      }

      VA:F [1.9.22_1171]
      0
  8. johny

    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!

    VA:F [1.9.22_1171]
    0
    1. 1337c0d3r Post author

      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)

      VN:F [1.9.22_1171]
      0
      1. Yao

        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?

        VA:F [1.9.22_1171]
        0
      2. Clive

        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)

        VN:F [1.9.22_1171]
        0
        1. Clive

          Sorry, reposting the code to reserve the indentation:

          VN:F [1.9.22_1171]
          0
  9. johny

    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?

    VA:F [1.9.22_1171]
    0
  10. johny

    Just want to add that the 1st solution still works, because nextRight is determined level by level. This is different from DFS.

    VA:F [1.9.22_1171]
    0
    1. 1337c0d3r Post author

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

      VN:F [1.9.22_1171]
      0
  11. johny

    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.

    VA:F [1.9.22_1171]
    0
  12. WgpShashank

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

    VA:F [1.9.22_1171]
    0
  13. Yao

    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

    VA:F [1.9.22_1171]
    0
  14. Henian

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

    VA:F [1.9.22_1171]
    0
  15. Sumit

    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.

    VA:F [1.9.22_1171]
    0
  16. Sumit

    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

    VA:F [1.9.22_1171]
    0
  17. Sumit

    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 🙁

    VA:F [1.9.22_1171]
    +1
  18. Ashok

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

    VA:F [1.9.22_1171]
    0
  19. Ashok

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

    VA:F [1.9.22_1171]
    0
  20. Ankur

    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 .

    VA:F [1.9.22_1171]
    0
  21. maxq

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

    VA:F [1.9.22_1171]
    0
  22. mohit goyal

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

    VA:F [1.9.22_1171]
    0
    1. jastination

      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.

      VN:F [1.9.22_1171]
      0
  23. Ankur Garg

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

    VA:F [1.9.22_1171]
    0
  24. Vijay Nair

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

    VA:F [1.9.22_1171]
    +1
  25. Rakesh

    VN:F [1.9.22_1171]
    0
  26. Pingback: Code: Milo › Nov. 1, Microsoft intern interview

  27. inheritance

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

    VN:F [1.9.22_1171]
    0
  28. mingmingbupt

    // 无额外空间
    /**
    * Definition for binary tree with next pointer.
    * struct TreeLinkNode {
    * int val;
    * TreeLinkNode *left, *right, *next;
    * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
    * };
    */
    class Solution {
    public:
    void connect(TreeLinkNode *root) {
    if (root == NULL) {
    return;
    }
    root->next = NULL;
    TreeLinkNode *first = NULL;
    TreeLinkNode *pre = NULL;
    while (root) {
    while (root) {
    if (root->left) {
    if (pre) {
    pre->next = root->left;
    } else {
    first = root->left;
    }
    pre = root->left;
    }
    if (root->right) {
    if (pre) {
    pre->next = root->right;
    } else {
    first = root->right;
    }
    pre = root->right;
    }
    root = root->next;
    }
    if (pre == NULL) {
    root = NULL;
    } else {
    root = first;
    }
    pre = NULL;
    }
    }

    };

    VN:F [1.9.22_1171]
    0
  29. ologlogn

    This access one node at a time. Complexity O(n)

    VN:F [1.9.22_1171]
    0
  30. Yingzhong Xu

    public void connect(TreeLinkNode root) {
    if (root == null)
    return;
    connectLeftAndRight(root);
    }

    private void connectLeftAndRight(TreeLinkNode root) {
    if (root.left != null) {
    root.left.next = root.right;
    if (root.next != null)
    root.right.next = root.next.left;
    connectLeftAndRight(root.left);
    connectLeftAndRight(root.right);
    }

    }

    VN:F [1.9.22_1171]
    +1
  31. Andrew

    I think your solutions are a bit complicated.
    Here is a super simple one in Java. I supply the node which is to be the “next” in a helper function and call it recursively.

    VA:F [1.9.22_1171]
    0
    1. Andrew

      Side note:
      Since I am just traversing the tree,
      the time complexity is: O(n),
      and space complexity is better than constant space, because I am not using any extra space at all.

      VA:F [1.9.22_1171]
      0
  32. porker2008

    I think the DFS solution does not meet the constant extra space requirement because you are using system stack to do the recursion. I have an implementation that only require constant extra space.

    VA:F [1.9.22_1171]
    0
    1. porker2008

      This solution works for any tree.

      VA:F [1.9.22_1171]
      +1
      1. yaz720

        The solution is correct, but you don’t need the first several lines about root before the loop:

        VN:F [1.9.22_1171]
        0
  33. Mingliang LIU

    VN:F [1.9.22_1171]
    +1
  34. yaz720

    Here is a C program to test whether your solution can correctly solve a generic tree.

    It generates a random tree and check whether your solution is correct. I have tested this program and it works fine:

    VN:F [1.9.22_1171]
    0
  35. ChrisG

    A simple solution: using a stack to remember the next right and recursively from right child:


    void FillLinks(Node * node, stack& siblings)
    {
    if (node == nullptr)
    return;

    if (!siblings.empty())
    {
    node->nextRight = siblings.top();
    siblings.pop();
    }

    FillLinks(node->rightChild, siblings);
    FillLinks(node->leftChild, siblings);

    siblings.push(node);
    }

    VN:F [1.9.22_1171]
    0
  36. Ralph

    trying again with better formatting

    VN:F [1.9.22_1171]
    0
  37. berkay

    simple python solution

    def link_right(root, is_left=None):
    if not root:
    return
    if root.left and root.right:
    root.left.link = root.right
    t1 = link_right(root.left, 1)
    t2 = link_right(root.right, -1)
    if t1 and t2:
    t1.link = t2
    if is_left:
    if is_left == 1:
    return root.right
    elif is_left == -1:
    return root.left

    VA:F [1.9.22_1171]
    0
  38. berkay

    with better formatting

    VA:F [1.9.22_1171]
    0
  39. madno

    VN:F [1.9.22_1171]
    0
  40. Gopi

    Hi Can anyone help me to get the answer for this in java or C# code.

    Given a binary tree with an empty next pointer, populate it with its right sibling or its immediate right cousin.
    a. What is the space complexity
    b. What can be the maximum size of the queue?
    c. Can we do it without a queue?

    Thanks

    VA:F [1.9.22_1171]
    0
  41. Carmel

    When choosing a topic for an essay, the writer has to be sure that they have enough information to make this essay.
    His job is involved of technicalities in addition of the
    skills of writing. Few owned word processors, much less personal computers,
    and the laptop was a thing of science fiction.

    VA:F [1.9.22_1171]
    0
  42. Boni

    Recursive sln, logN space for stack. Left child’s sibling is current node’s right. Right child’s sibling is current sibling’s left child.

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*