package tree;

import java.util.*;

/**

* Created by gouthamvidyapradhan on 07/07/2017.

*

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

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));

}

}

}