package tree;

/**
 * Created by gouthamvidyapradhan on 03/10/2017.
 *
 * <p>Follow up for problem "Populating Next Right Pointers in Each Node".
 *
 * <p>What if the given tree could be any binary tree? Would your previous solution still work?
 *
 * <p>Note:
 *
 * <p>You may only use constant extra space. For example, Given the following binary tree, 1 / \ 2 3
 * / \ \ 4 5 7 After calling your function, the tree should look like: 1 -> NULL / \ 2 -> 3 -> NULL
 * / \ \ 4-> 5 -> 7 -> NULL
 */
public class NextRightPointerII {

  public static void main(String[] args) throws Exception {
    TreeLinkNode root = new TreeLinkNode(1);
    root.left = new TreeLinkNode(2);
    root.right = new TreeLinkNode(3);
    root.right.right = new TreeLinkNode(4);
    root.right.right.left = new TreeLinkNode(5);
    root.right.right.right = new TreeLinkNode(6);
    new NextRightPointerII().connect(root);
  }

  public void connect(TreeLinkNode root) {
    TreeLinkNode prev = new TreeLinkNode(0);
    TreeLinkNode first = null;
    while (root != null) {
      if (root.left != null) {
        prev.next = root.left;
        prev = root.left;
        if (first == null) {
          first = root.left;
        }
      }
      if (root.right != null) {
        prev.next = root.right;
        prev = root.right;
        if (first == null) {
          first = root.right;
        }
      }
      root = root.next;
      if (root == null) {
        root = first;
        first = null;
        prev = new TreeLinkNode(0);
      }
    }
  }

  public static class TreeLinkNode {
    int val;
    TreeLinkNode left, right, next;

    TreeLinkNode(int x) {
      val = x;
    }
  }
}