Find nodes of the same height when a binary tree node is given?
I want to know if there is any other optimal solution than this.
Problem: Given a Node in a binary tree, I need to write a program to find
out all the nodes that are of the same level as the given node
(inclusive). Example: If the given node is of the level 2 then program
should return a collection of all the nodes with height 2.
My Solution : I had two methods, one to find out the root of the given
node and return the root(this method also finds out the height (bheight in
my code) from the node to the root) and this root is fed to the second
method to do a breadth first search and keep updating heights of the nodes
as I traverse and if the height of the first element in the queue equals
to the height that I calculated in the root method, then I return the
queue.
My Code:
import java.util.LinkedList;
import java.util.Queue;
public class binaryTree {
int value;
binaryTree left;
binaryTree right;
binaryTree parent;
int height;
static int bheight;
Queue<binaryTree> que = new LinkedList<binaryTree>();
public binaryTree(int v) {
value = v;
}
//This method returns a Queue of all the nodes that are on the same level
as the supplied node b.
public Queue<binaryTree> BFS(binaryTree b) {
b = root(b);
que.clear();
b.height=0;
que.add(b);
while (!que.isEmpty()) {
binaryTree node = que.remove();
if (node.left != null) {
node.left.height=(node.left.parent.height)+1;
System.out.println(node.left.value+" Root is
"+node.left.parent.value+" and its height is " +
node.left.height);
que.add(node.left);
}
if (node.right != null) {
node.right.height=(node.right.parent.height)+1;
System.out.println(node.right.value+" Root is
"+node.right.parent.value+" and its height is " +
node.left.height);
que.add(node.right);
}
if(que.peek().height==bheight)
{
break;
}
}
return que;
}
//Finds out the root of the given node and returns the root node
public binaryTree root(binaryTree t) {
if (t.parent == null) {
return t;
} else {
bheight++;
return root(t.parent);
}
} }
No comments:
Post a Comment