Trees: Connect Right Peers

Problem Statement:
            Connect nodes to their peers on right at each level.

Given Binary Tree:

Output Binary Tree should be:

Solution:
Download Source Code

This question was asked to me in one of the interviews(Akamai), for which i initially gave Iterative BFS solution, after some cross-questioning i came up with the recursive one.
The solution i have discussed here is very intuitive as we need to connect nodes of the same level, so we would adopt Iterative BFS approach for the solving the problem. The problem can also be solved by recursive approach, which i will discuss in some other post.
 
Implementation of connect to right peers:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

private Queue<Node> queue = new LinkedList<Node>(); /** * Connect Nodes to their peers on the right at the same level, * Performing BFS on the given tree and connecting peers */ public void connect(Node root) { queue.add(root); queue.add(null); while (!queue.isEmpty()) { Node poped = queue.poll(); if (poped == null) { if (queue.isEmpty()) // if last node , terminate continue; queue.add(null); } else { poped.peer = queue.peek(); if (poped.left != null) queue.add(poped.left); if (poped.right != null) queue.add(poped.right); } } }

Display Tree: 
Implementation of the displaying the tree after the peers are connected.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

/** * Print the modified Tree, * We are using left child of every level and then printing its peers */ private static int maxLevel = 0; public void display(Node root, int level) { if (root == null) return; if (maxLevel < level) { Node temp = root; while (temp != null) { System.out.print(temp + "---> "); temp = temp.peer; } System.out.println(); maxLevel = level; } display(root.left, level + 1); display(root.right, level + 1); }

Please post your suggestions and comments.
Happy Coding !! :)