how to get the path from root to a given node on a binary tree?

Question

I am trying to find out how to get the path from root to a given node on a binary tree.

It is not binary search tree.

Each non-leaf node has only two pointers to their children.

In-order, pre-order, post-order traversal do not work.

I have tried to do pre-order but cannot figure out how. For example, we have a binary tree: It is NOT a binary search tree. We use the sorting order node to make it easier to find the path.

     1 
   /   \
  2     3
 / \   / \
4   5 6   7 

We want to find the path from 1 to 7:

With pre-order, we have:

1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 

From the flow, we get the path from 1 -> 7 with all nodes on it.

Obviuosly, it should not be.

Any help is really appreciated.

Answer 1

Preorder traversal, otherwise known as depth-first search does work.

• If you implement preorder traversal recursively, then when you reach the desired node, you can unwind your stack (of recursive calls) and construct your path in reverse.

• If you implement the preorder traversal non-recursively, then you will be building a stack directly, so in this case once you reach your desired node you have your path already.

In the tree in your question above, the algorithm to find the path from 1 to 7 proceeds as follows.

• Start with 1, push it on the stack, stack is now [1]
• Go left to the 2, push it on the stack, stack is now [1 2]
• Go left to the 4, push it, stack is now [1 2 4]
• There are no children of 4, and it is not what you want, so pop it, stack is now [1 2]
• Now that you are back at the 2, and you have already gone left, now go right, stack is now [1 2 5]
• There are no children of 5, so pop, stack is now [1 2]
• You have exhausted the children of 2, so pop it, stack is now [1]
• Now you are back at the 1 and you have finished the left, so go right to the 3, push it, stack is now [1 3]
• Go left, stack is now [1 3 6]
• 6 is a leaf, not what you are looking for, so pop, stack is [1 3]
• Now you have to go to the right from 3, push it, stack is now [1 3 7]
• But WAIT! LOOK! You have arrived at the node you are looking for! And look at your stack! It's the path you want.

Answer 2

You are given a binary tree ( root Node) .. and a key is given which may or may not be in the tree. You have to find the full path from the root to the node.

Example:

                A
           /           \
       B                C
         \               /
          D           E
        /    \           \
      K      L        M
    /
Z

you have given node Z ( or the key for the Node ) and given Node A( root) So your output should be

A B D K Z

if M is given, the output should be A C E M

public class main_class {
public static void main(String args[] ) {

    //first create tree
    Node rootNode = new Node ('A' , new Node('B',null,
                                             new Node('D',
                                                      new Node('K',
                                                               new Node('Z',null,
                                                               null),null),
                                                      new Node('L',null,null))),
                                    new Node('C',
                                             new Node('E',
                                                      null,
                                                      new Node('M',null,null)),null) );

    ArrayList <Node> path = new ArrayList<Node>();
    System.out.println(getPath(rootNode,'Z',path));
    System.out.println(path);
    path = new ArrayList<Node>();
    System.out.println(getPath(rootNode,'M',path));
    System.out.println(path);

}
static boolean getPath(Node rootNode, char key, ArrayList<Node> path ){
    //return true if the node is found
    if( rootNode==null)
        return false;
    if (rootNode.getVal()==key){
        path.add(rootNode);
        return true;
    }
    boolean left_check = getPath( rootNode.left,key,path);
    boolean right_check = getPath( rootNode.right,key,path);
    if ( left_check || right_check){
        path.add(rootNode);
        return true;
    }
    return false;

}
static class Node {
    char val;
    Node left;
    Node right;
    public Node( char val, Node left, Node right){
        this.left=left;
        this.right=right;
        this.val=val;
    }
    public char getVal(){
        return val;
    }
   public String toString(){
        return " " + val + " ";
    }
}

}