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.