LeetCode - Populating Next Right Pointers in Each Node | Darren's Blog

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.

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

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

The order of visits of tree node is the same as LeetCode - Binary Tree Level Order Traversal. But now we do not need to maintain a queue, since the reference  next gives exactly the next node in the same level. So we can work on each level, and visit each node in a level in sequence.

public void connect(TreeLinkNode root) {

        if (root == null)   // Empty tree

            return;

 

        TreeLinkNode headOfNextLevel = root;

 

        // Between levels

        while(headOfNextLevel != null) {

            // Initialize tailOfNextLevel and current, and update headOfNextLevel to null

            TreeLinkNode tailOfNextLevel = null, current = headOfNextLevel;

            headOfNextLevel = null;

 

            // Within a level

            while(current != null) {

                // Update headOfNextLevel if we find the first node in the next level

                if (headOfNextLevel == null && current.left != null)

                    headOfNextLevel = current.left;

 

                // Not a leaf; link its children

                if (current.left != null)

                    current.left.next = current.right;

 

                // Link the currently last node in the next level to the left subtree of current node

                if (tailOfNextLevel != null)

                    tailOfNextLevel.next = current.left;

 

                // Update tailOfNextLevel to the right subtree, and

                // move to the next node in the same level

                tailOfNextLevel = current.right;

                current = current.next;

            }

        }

    }

Read full article from LeetCode - Populating Next Right Pointers in Each Node | Darren's Blog