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

Understand the problem:
The problem asks for populating each of node's next pointer to its next right node. If there is no next node, its next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note that you are required to only use constant extra space. 

A native approach:
A very straight-forward solution is to use BFS, where we traverse the tree in level-order. However, this solution requires using a queue, which needs to take extra space. 

A better approach:
For a better approach without using extra space, we can observe the tree structure. Note that for each problem the tree in a perfect binary tree, which means that each node must have its left and right children. It indicates that all nodes except for the last node in each level has its next right node. So for each node has left child, root.left -> root.right; For each node root.right != null && root.next != null , root.right.next = root.next.left.

Code (Java):

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        if (root.left != null) {
            root.left.next = root.right;
        }
        
        if (root.next != null && root.next.left != null) {
            root.right.next = root.next.left;
        }
        
        connect(root.left);
        connect(root.right);
    }
}

Summary:
This problem is very tricky but if figure out the process of connecting nodes, it becomes very simple.

Update on 2/8/16:
Constant space solution:

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        TreeLinkNode curr = root;
        
        while (curr != null && curr.left != null && curr.right != null) {
            TreeLinkNode p = curr;
            while (p != null) {
                if (p.left != null) {
                    p.left.next = p.right;
                }
            
                if (p.right != null && p.next != null) {
                    p.right.next = p.next.left;
                }
                
                p = p.next;
            }
            
            curr = curr.left;
        }
    }
}