11 February 2010

Trace path of a node in a BINARY TREE in Java

The problem is simple. Given a node, we should be able to show the path from the root to that node in a BINARY TREE (NOT A BINARY SEARCH TREE). This solution would help us how to traverse through a binary tree. Here I am going to do an inorder traversal. More on traversals on a binary tree can be found here.
Consider the following binary tree, we can see the path to be found and the node supplied to find it. We will be provided with a tree, its root and the node to be found.



76 is the item that we need to find. Although the example looks like a BINARY SEARCH TREE, we are not going to use the binary search tree way to find 76. So, we would have no other way than doing either of inorder, post-order or pre-order traversals. 
To attack this problem,we maintain a stack. The stack will always maintain the path. Whenever we encounter the node to be found, we will stop our process and the path in the current stack will give the path to be found. The solution for this problem shown would be : 43,887,46,78,76

I was having problem in returning from the recursive method in a proper manner. Thanks to the help of stackoverflow.com  and its code gurus, I was redirected to the right path.

Now, for the Java code part,
package dsa.tree;

import java.util.Stack;

public class TracePath {
 private Node n1;
 private Stack<Node> mainStack = null;
 
 public static void main(String args[]){
  TracePath nodeFinder = new TracePath();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  trace(t,n1);
  for(Node iNode:mainStack){
   System.out.println(iNode.data);
  }
 }

 private Tree getSampleTree() {
  Tree bsTree = new BinarySearchTree();
  int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
  for(int i=0;i<randomData.length;i++){
   bsTree.add(randomData[i]);
  }
  n1 = bsTree.search(76);
  return bsTree;
 }
 
 public Stack<Node> trace(Tree t, Node node){
  mainStack = new Stack<Node>();
  trace(t.getRoot(),node);
  return mainStack;
 }
 
 private boolean trace(Node parent, Node node){
  mainStack.push(parent);
  if(node.equals(parent)){
   return true;
  }
  if(parent.left != null){
   if (trace(parent.left, node))
    return true;
  }
  if(parent.right!=null){
   if (trace(parent.right, node))
    return true;
  }
  mainStack.pop();
  return false;
 }
}

5 comments:

Prateek said...

Hi,

Is it a in-order traversal? I feel it is a pre-order traversal. Can you please explain it a bit.

Thanx

BragBoy said...

Hi Prateek,

Sorry for a delayed reply, I was out of town and was not having internet connectivity.

For the question you've asked, YES this is an in order traversal. In order traversals follow the rule of visiting the left, parent and finally the right node in a binary tree.

As wee apply this rule to this problem, we essentially pushing the nodes we visit as we go by in a stack. Since we have to visit left (in-order traversal), we start doing that from root. Every time we encounter a node we push it into a stack.

You should understand that we are searching for our node of interest in this TRACE PATH problem. Hence we have to pop elements from the stack should we not find our node.

Hope this helped. I can explain more if you can narrow your question a bit.

Unknown said...

Would this be possible to do this iteratively without using a visited flag?

Devesh said...

Hi ,
Thanks for all the posts.
Just wanted to clear small doubt regarding the method used in traversal, Isn't this typical pre order and not really inorder as the root is being compared first and then the left and right nodes..Doesn't make any difference as such..

BragBoy said...

@Devesh: Thanks for stopping by!

Regarding your doubt, you need to be clear about one thing. You can always get a tree by just getting its ROOT. Now that you have got the root in hand does not mean that you are visiting the root first. Yes, you are using root for traversing, but real order traversal means that you mark a node as 'visited'

In-order traversal, you traverse to the left most node and mark it as visited, if no left exist, check root, mark as visited, then check right, mark as visited.

If you could notice you are indeed visiting root now and then but not marking as visited.

Consider a simple tree with B at ROOT, A as left node and C as right node:
In-order traversal would produce ABC
Pre-order would produce BAC
Post-order would output ACB

All the above three started with the root for your information.

Thanks again for reading my posts!!