fork download
copy 
  1.  
  2.  
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5.  
  6. /**
  7.  * Connect Nodes to their peers on the right at the same level
  8.  * Node is modified and additional pointer added
  9.  * @author PRATEEK
  10.  *
  11.  */
  12. class ConnectPeers {
  13.  
  14. 	private Queue<Node> queue = new LinkedList<Node>();
  15.  
  16. 	/**
  17. 	 * Connect Nodes to their peers on the right at the same level,
  18. 	 * Performing BFS on the given tree and connecting peers
  19. 	 */
  20. 	public void connect(Node root) {
  21. 		queue.add(root);
  22. 		queue.add(null);
  23. 		while (!queue.isEmpty()) 
  24. 		{
  25. 			Node poped = queue.poll();
  26. 			if (poped == null) 
  27. 			{
  28. 				if (queue.isEmpty()) // if last node , terminate
  29. 					continue;
  30. 				queue.add(null);
  31. 			} 
  32. 			else 
  33. 			{
  34. 				poped.peer = queue.peek();
  35.  
  36. 				if (poped.left != null)
  37. 					queue.add(poped.left);
  38. 				if (poped.right != null)
  39. 					queue.add(poped.right);
  40. 			}
  41. 		}
  42. 	}
  43.  
  44.  
  45. 	/**
  46. 	 * Print the modified Tree,
  47. 	 * We are using left child of every level and then printing its peers
  48. 	 */
  49. 	private static int maxLevel = 0;
  50. 	public void display(Node root, int level) {
  51. 		if (root == null)
  52. 			return;
  53.  
  54. 		if (maxLevel < level) {
  55. 			Node temp = root;
  56. 			while (temp != null) {
  57. 				System.out.print(temp + "--->  ");
  58. 				temp = temp.peer;
  59. 			}
  60. 			System.out.println();
  61. 			maxLevel = level;
  62. 		}
  63.  
  64. 		display(root.left, level + 1);
  65. 		display(root.right, level + 1);
  66. 	}
  67.  
  68. 	public static void main(String[] args) {
  69. 		Node root = new Node(1);
  70. 		root.left = new Node(2);
  71. 		root.left.left = new Node(4);
  72. 		root.left.right = new Node(5);
  73. 		root.left.right.left = new Node(8);
  74. 		root.left.right.right = new Node(9);
  75. 		root.left.right.left.left = new Node(10);
  76.  
  77. 		root.right = new Node(3);
  78. 		root.right.left = new Node(6);
  79. 		root.right.right = new Node(7);
  80.  
  81. 		ConnectPeers obj = new ConnectPeers();
  82. 		obj.connect(root);
  83. 		obj.display(root, 1);
  84.  
  85. 	}
  86. }
  87.  
  88. class Node {
  89. 	int data;
  90. 	Node left;
  91. 	Node right;
  92. 	Node peer;
  93.  
  94. 	Node(int data) {
  95. 		this.data = data;
  96. 	}
  97.  
  98. 	@Override
  99. 	public String toString() {
  100.  
  101. 		return this.data + "";
  102. 	}
  103. }
  104.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1--->  
2--->  3--->  
4--->  5--->  6--->  7--->  
8--->  9--->  
10--->
https://ideone.com/f7sUG5
Connect Peers in Binary Tree
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!