package tree;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * Created by gouthamvidyapradhan on 07/07/2017.
 *
 * <p>Given a binary tree
 *
 * <p>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.
 *
 * <p>Initially, all next pointers are set to NULL.
 *
 * <p>Note:
 *
 * <p>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
 *
 * <p>Solution: Perform a level order traversal using BFS, keep track of prev node at each level.
 * Link the prev node to current node if both the nodes are in the same level.
 */
public class NextRightPointer {
  private class LevelNode {
    int level;
    TreeLinkNode node;

    LevelNode(TreeLinkNode node, int level) {
      this.node = node;
      this.level = level;
    }
  }

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

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

  public static void main(String[] args) throws Exception {
    TreeLinkNode node = new TreeLinkNode(2);
    node.left = new TreeLinkNode(1);
    node.right = new TreeLinkNode(3);
    new NextRightPointer().connect(node);
    System.out.println(node.next);
    System.out.println(node.left.next.val);
    System.out.println(node.right.next);
  }

  public void connect(TreeLinkNode root) {
    Queue<LevelNode> queue = new ArrayDeque<>();
    LevelNode zero = new LevelNode(root, 0);
    queue.offer(zero);
    LevelNode prev = null;
    while (!queue.isEmpty()) {
      LevelNode levelNode = queue.poll();
      if (levelNode.node == null) break;
      TreeLinkNode curr = levelNode.node;
      if (prev != null) {
        if (prev.level == levelNode.level) {
          prev.node.next = levelNode.node;
        }
      }
      prev = levelNode;
      queue.offer(new LevelNode(curr.left, levelNode.level + 1));
      queue.offer(new LevelNode(curr.right, levelNode.level + 1));
    }
  }
}