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

// Definition for binary tree with next pointer.
private class TreeLinkNode {
    int val;
    TreeLinkNode left, right, next;
    TreeLinkNode(int x) { val = x; }
}

public class Solution {
    // Solution 1: O(n) O(log n)
    public void connect(TreeLinkNode root) {
        connect(root, null);
    }
    private void connect(TreeLinkNode root, TreeLinkNode next) {
        if (root == null)
            return;
        else 
            root.next = next;

        connect(root.left, root.right);
        if (next != null)
            connect(root.right, next.left); // Bug here...
        else
            connect(root.right, null);
    }

    // Solution 2: O(n), O(log n)
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        if (root.left != null)
            root.left.next = root.right;
        if (root.right != null)
            root.right.next = root.next == null? null : root.next.left;
        connect(root.left);
        connect(root.right);
    }
}

add PopulatingNextRightPointersinEachNode.java