LeetCode: Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

---

For the root node, its next is NULL, and its left node is linked to its right node. If the node is not a root node, its left node is still linked to its right node and its right node will linked to the node's next node's left node.

C++ Code:

/*
 * func: populate_right_helper
 * goal: recursive helper function for connecting nodes in the same level
 * @param root: root node
 * return:
 */
void populate_right_helper(TreeLinkNode *root){
    if(root == nullptr){
        return;
    }
    
    if(root->left){
        root->left->next = root->right;
    }
    
    if(root->right){
        root->right->next = (root->next) ? root->next->left : nullptr;
    }
    
    populate_right_helper(root->left);
    populate_right_helper(root->right);
}

/*
 * func: populate_right
 * goal: populate each next pointer to its next right node
 * @param root: root node of the tree
 * return:
 */
void populate_right(TreeLinkNode *root){
    if(root == nullptr){
        return;
    }
    root->next = nullptr;
    populate_right_helper(root);
}

Python Code:

# func: populate each next pointer to its next right node
# @param root: root node of the tree
# @return:
def populate_right(root):
    if not root:
        return
    root.next = None
    def populate_right_helper(node):
        if not node:
            return
        if node.left:
            node.left.next = node.right

        if node.right:
            if node.next:
                node.right.next = node.next.left
            else:
                node.right.next = None

        populate_right_helper(node.left)
        populate_right_helper(node.right)

    populate_right_helper(root)

Reference Link:

1. Connect nodes at same level | GeeksforGeeks: http://www.geeksforgeeks.org/connect-nodes-at-same-level/