How to connect nodes at same level using constant extra space? OR
Populate next right pointers for each Tree Node? OR
Connect nodes of a binary tree at same Level?
Let us first understand what we want to achieve? what is the input and what will be the expected output?
Question:
Binary Tree is given to you,
- some node of tree has both left and right child present,
- some node of tree has only left child present and
- some node of tree has only right child present,
- nextRight pointer of all the node initially is null.
- If the immediate adjacent node is not present then connect to next adjacent node and
- If next adjacent node is not present then connect to next to next adjacent node and
- If next to next adjacent node is not present then search until you find the adjacent node along the same Level and connect to it.
- If the adjacent node is not present at same level then connect it to null.
Structure of the given Binary Tree Node is like following:
package com.javabypatel.tree;
class Node{
private int data;
private Node left;
private Node right;
private Node nextRight; <---- New pointer introduced to connect to adjacent Node.
}
What is adjacent node?
Look at the below elaborated Case 2 image,Immediate adjacent node of Node 7 is not present as Node 3 doesn't has right child.
Next to adjacent node is also not present as Node 8 doesn't has left child,
Also next to next adjacent node is not present as Node 8 doesn't has right child.
While searching along the same Level, we see Node 25 is present and it has right child present,
So connect Node 7 nextRight pointer to Node 30.
Algorithm
Lets say we have a tree where nextRight pointer for all the nodes in a tree is set.
By Looking at a Tree we can see, Node 5 adjacent node is Node 20. How we come to know that?
To find the adjacent node of Node 5, first look at the parent node of Node 5 which is Node 10.
So, right Node of Node 10 (if present) that is Node 20 is the adjacent node of Node 10.
So we can connect Node 5 nextRight pointer to Node 20.
Now, lets find out what is the adjacent Node of Node 3?
Look at the Parent Node of Node 3 that is Node 5.
So, right Node of Node 5 (if present) that is Node 8 is the adjacent node of Node 3.
Now, lets find out what is the adjacent Node of Node 8?
Look at the Parent Node of Node 8 that is Node 5.
So Node 5 is not helpful, but Node 5's nextRight Node is Node 20 and left child(if present) of Node 20 is adjacent Node of Node 8.
if left child of Node 20 is not present then check right Node of Node 20, if present then that node that is Node 25 will be adjacent to adjacent node of Node 8.
Now, lets find out what is the adjacent Node of Node 7?
Look at the Parent Node of Node 7 that is Node 3.
check the right node of Node 3, which is not present, so Node 3 is not helpful and we need to check for next node in the level.
How we will get the next node at the level of Node 3 is go to nextRight of Node 3, which will land us to Node 8.
Now if Node 8 left child is present then that can become nextRight node of Node 7 but left child is not present.
Now if Node 8 right child is present then that can become nextRight node of Node 7 but right child is not present.
So, Node 8 is not helpful and check the next node at same level (level 3), next node at same level we will get by nextRight of Node 8 that is Node 25.
Now if Node 25 left child is present then that can become nextRight node of Node 7 but left child is not present.
Now if Node 25 right child is present then that can become nextRight node of Node 7 and right child is present that is Node 30, so connect nextRight of Node 7 to Node 30.
Conclusion
So what observation we can see from above discussion is,
Before working for level 4, nextRight pointer of all the nodes at Level 3 should be set then only we can traverse across Level 3 to find adjacent nodes of Level 4.
Before working for level 3, nextRight pointer of all the nodes at Level 2 should be set then only we can traverse across Level 2 to find adjacent nodes of Level 3.
Before working for level 3, nextRight pointer of all the nodes at Level 2 should be set then only we can traverse across Level 2 to find adjacent nodes of Level 3.
Before working for level 2, nextRight pointer of all the nodes at Level 1 should be set then only we can traverse across Level 1 to find adjacent nodes of Level 2.
From this we can say, we need to traverse the tree in such a way where our first task is to set nextRight pointer of all nodes at level 1
and then only move to level 2 and so on.
That is read the tree in Pre order traversal form but instead of reading in Root, Left, Right format, we will read in Node, nextRight, Left format.
Java Program for Connecting nodes at Same Level in Binary Tree. (Only if tree is Complete Binary Tree)
ConnectNodesAtSameLevel.java
package com.javabypatel.tree;
import java.util.LinkedList;
import java.util.Queue;
public class ConnectNodesAtSameLevel{
public static void main(String[] args) {
Node rootNode=null;
rootNode = addNode(rootNode, 10, true);
rootNode = addNode(rootNode, 5, true);
rootNode = addNode(rootNode, 20, true);
rootNode = addNode(rootNode, 2, true);
rootNode = addNode(rootNode, 8, true);
rootNode = addNode(rootNode, 15, true);
rootNode = addNode(rootNode, 30, true);
linkNodesAtSameLevelWithoutExtraSpace(rootNode);
System.out.println(rootNode);
}
private static void linkNodesAtSameLevelWithoutExtraSpace(Node rootNode){
// We are going to read Tree in Pre order fashion.
// Root, nextRight, Left
//if rootNode is null, return
if(rootNode==null)
return;
// What we are trying to do here is setting the nextRight node of next level.
// if left child of rootNode and right child of rootNode is null, then there are no nodes further.
if(rootNode.getLeft()==null && rootNode.getRight()==null){
return;
}
// if left child of rootNode and right child of rootNode is not null, then left node nextRight can easily be connected to right node.
if(rootNode.getLeft()!=null && rootNode.getRight()!=null){
rootNode.getLeft().setNextRight(rootNode.getRight());
Node tmp = rootNode.getNextRight();
while(tmp!=null && tmp.getLeft()==null && tmp.getRight()==null){
tmp = tmp.getNextRight();
}
// we do not found any nodes at rootNode level whose left child or right child is present.
if(tmp==null){
rootNode.getRight().setNextRight(null);
}else if(tmp.getLeft()!=null){ // Found a node whose left child is not null, so connecting left child nextRight to it.
rootNode.getRight().setNextRight(tmp.getLeft());
}else if(tmp.getRight()!=null){ // Found a node whose right child is not null, so connecting left child nextRight to it.
rootNode.getRight().setNextRight(tmp.getRight());
}
}else if(rootNode.getLeft()==null){
// Only condition that can be true at this point is either leftNode can be null or rightNode can be null
// if left child is null, then rootNode definitely has right child present.
// if the right child is present then we need to search all the nodes at rootNode level and find the node whose left or right
// child is not null and associate right child nextRight to it.
Node tmp = rootNode.getNextRight();
while(tmp!=null && tmp.getNextRight()!=null && tmp.getNextRight().getLeft()==null && tmp.getNextRight().getRight()==null){
tmp = tmp.getNextRight();
}
// we do not found any nodes at rootNode level whose left child or right child is present.
if(tmp==null){
rootNode.getRight().setNextRight(null);
}else if(tmp.getLeft()!=null){ // Found a node whose left child is not null, so connecting right child nextRight to it.
rootNode.getRight().setNextRight(tmp.getLeft());
}else if(tmp.getRight()!=null){ // Found a node whose right child is not null, so connecting right child nextRight to it.
rootNode.getRight().setNextRight(tmp.getRight());
}
}else{
// if right child is null, then rootNode definitely has left child present.
// if the left child is present then we need to search all the nodes at rootNode level and find the node whose left or right
// child is not null and associate left child nextRight to it.
Node tmp = rootNode.getNextRight();
while(tmp!=null && tmp.getLeft()==null && tmp.getRight()==null){
tmp = tmp.getNextRight();
}
// we do not found any nodes at rootNode level whose left child or right child is present.
if(tmp==null){
rootNode.getLeft().setNextRight(null);
}else if(tmp.getLeft()!=null){ // Found a node whose left child is not null, so connecting left child nextRight to it.
rootNode.getLeft().setNextRight(tmp.getLeft());
}else if(tmp.getRight()!=null){ // Found a node whose right child is not null, so connecting left child nextRight to it.
rootNode.getLeft().setNextRight(tmp.getRight());
}
}
//For the current Level, nextRight is set for all the nodes.
// Reading the Left child now as nextRight is set for a cuurent level and we can go to next level.
linkNodesAtSameLevelWithoutExtraSpace(rootNode.getLeft());
// Reading the Right child now as nextRight is set for a cuurent level and we can go to next level.
linkNodesAtSameLevelWithoutExtraSpace(rootNode.getRight());
}
private static Node addNode(Node rootNode, int i, boolean isRootNode) {
if(rootNode==null){
return new Node(i);
}else{
if(i > rootNode.getData()){
if(isRootNode){
Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
rootNode.setRight(nodeToAdd);
}else{
Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
rootNode.setLeft(nodeToAdd);
}
}else{
if(isRootNode){
Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
rootNode.setLeft(nodeToAdd);
}else{
Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
rootNode.setRight(nodeToAdd);
}
}
}
return rootNode;
}
}
Node.java
package com.javabypatel.tree;
public class Node{
private int data;
private Node left;
private Node right;
private Node nextRight;
public Node(int data) {
this.data=data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public Node getNextRight() {
return nextRight;
}
public void setNextRight(Node nextRight) {
this.nextRight = nextRight;
}
}
For better understanding, I have repeated code in the method, we can very well create a method and avoid code repetition.
Note: Above method will work only if tree is complete Binary Tree.
Java Program for Connecting nodes at Same Level in Binary Tree. (Will work if tree is not Complete Binary Tree)
package com.javabypatel.tree;
public class ConnectNodesAtSameLevel {
/*
10 Level 1
/ \
5 20 Level 2
/ \ / \
2 8 15 30 Level 3
/ \
1 40 Level 4
*/
public static void main(String[] args) {
TNode rootTNode = null;
rootTNode = addTNode(rootTNode, 10, true);
rootTNode = addTNode(rootTNode, 5, true);
rootTNode = addTNode(rootTNode, 20, true);
///rootTNode = addTNode(rootTNode, 2, true);
//rootTNode = addTNode(rootTNode, 8, true);
rootTNode = addTNode(rootTNode, 15, true);
rootTNode = addTNode(rootTNode, 30, true);
//rootTNode = addTNode(rootTNode, 1, true);
rootTNode = addTNode(rootTNode, 40, true);
connectWithoutExtraSpace(rootTNode);
System.out.println(rootTNode);
}
private static void connectWithoutExtraSpace(TNode rootTNode) {
//Do preorder traversal
//Before going to level x, we make sure that that all nodes right pointer is connected at level x-1
//so before working for Node 1 at level 4, we make sure that 2->8->15->30 is connected
//Here we complete level by level, while at level x, we try to connect all nodes at level x+1
if (rootTNode == null)
return;
if (rootTNode.getLeft() == null && rootTNode.getRight() == null) {
return;
}
// if both childs are present then connect them
if (rootTNode.getLeft() != null && rootTNode.getRight() != null) {
rootTNode.getLeft().setNextRight(rootTNode.getRight());
//we connected left->right but what about right-> ? so search for next right of right child and connect,
//lets take example, while working for Node 5 at level 2, it tries to connect all node at level 3 before moving to level 3.
//Above line will connect 2->8, but what about 8->15, connectNodesAtSameLevel will do that.
//connectNodesAtSameLevel also, calls connectWithoutExtraSpace to make sure that
//left and right of 20 is also connected and so on.
connectNodesAtSameLevel(rootTNode, false);
} else if (rootTNode.getLeft() == null) {
connectNodesAtSameLevel(rootTNode, false);
} else if (rootTNode.getRight() == null) {
connectNodesAtSameLevel(rootTNode, true);
}
connectWithoutExtraSpace(rootTNode.left);
connectWithoutExtraSpace(rootTNode.right);
}
static void connectNodesAtSameLevel(TNode rootTNode, boolean left){
TNode tmp = rootTNode.getNextRight();
while (tmp != null && tmp.getLeft() == null && tmp.getRight() == null) {
tmp = tmp.getNextRight();
}
// we do not found any nodes at rootTNode level whose left child or right child is present.
if (tmp != null) {
if (tmp.getLeft() != null) { // Found a node whose left child is not null, so connecting left child nextRight to it.
if(left)
rootTNode.getLeft().setNextRight(tmp.getLeft());
else
rootTNode.getRight().setNextRight(tmp.getLeft());
} else {
if(left)
rootTNode.getLeft().setNextRight(tmp.getRight());
else
rootTNode.getRight().setNextRight(tmp.getRight());
}
connectWithoutExtraSpace(tmp);
}
}
private static TNode addTNode(TNode rootTNode, int i, boolean isRootTNode) {
if (rootTNode == null) {
return new TNode(i);
} else {
if (i > rootTNode.getData()) {
if (isRootTNode) {
TNode nodeToAdd = addTNode(rootTNode.getRight(), i, isRootTNode);
rootTNode.setRight(nodeToAdd);
} else {
TNode nodeToAdd = addTNode(rootTNode.getLeft(), i, isRootTNode);
rootTNode.setLeft(nodeToAdd);
}
} else {
if (isRootTNode) {
TNode nodeToAdd = addTNode(rootTNode.getLeft(), i, isRootTNode);
rootTNode.setLeft(nodeToAdd);
} else {
TNode nodeToAdd = addTNode(rootTNode.getRight(), i, isRootTNode);
rootTNode.setRight(nodeToAdd);
}
}
}
return rootTNode;
}
}
TNode.java
package com.javabypatel.tree;
public class TNode {
int data;
TNode left;
TNode right;
TNode nextRight;
TNode(int data) {
this.data = data;
}
public TNode getNextRight() {
return nextRight;
}
public TNode getLeft() {
return left;
}
public TNode getRight() {
return right;
}
public void setLeft(TNode left) {
this.left = left;
}
public void setRight(TNode right) {
this.right = right;
}
public void setData(int data) {
this.data = data;
}
public void setNextRight(TNode nextRight) {
this.nextRight = nextRight;
}
public int getData() {
return data;
}
}
You may also like to see
Connect nodes at same level in a Binary Tree using Queue.
Construct a Binary Tree from In-order and Pre-order traversals.
Top Binary tree interview questions in Java
Find Kth SMALLEST element in BST(Binary Search Tree)
Check whether Binary Tree is foldable or not.
Check if two nodes are cousins in a Binary Tree.
Get Level/Height of node in binary tree
Print nodes at K distance from Leaf node in Binary tree.
Construct a Binary Tree from In-order and Post-order traversals.
Print Nodes in Top View of Binary Tree.
Zig Zag Traversal of Binary Tree.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment