Pages

Monday, June 17, 2013

Shortest Path in a Binary Tree

This one may be from the tougher category, but it becomes easy when you understand the idea. So the question is "what is the shortest route between 2 unique nodes in a binary tree". I'll handle the same problem but in a binary search tree in a separate article. I knew the answer before, since I reviewed the lowest common ancestor in a binary tree first. Yes, the idea is to find first the lowest common ancestor of the two nodes and then "draw the path" from the LCA to the 2 nodes. I explained finding the LCA in a binary tree in this article, so I'll go straight to the second part: identifying the path. Let's use the below tree as an example.

Simple Binary Tree
Fig. 1 - A Simple Binary Tree

Let's say we want to find the shortest path between nodes "2" (last one) and "11". Having identified the LCA as "7", we can now assume that the nodes are either located each in its separate branch or one node is the LCA and the second is either in the left or right branch. Second option is not the case, so we traverse the left and right branch (recursion possible) until we find any of the two nodes by comparing the branch node with the nodes. First one is easy we go onto the left branch and we find the "2" node right away. Then we go onto the right branch - "6", not our node, recurse on the left and right branch of "6". "5" is not our node, "11" is, so we add it to our path. The final path is "2, 7, 6, 11". How would we manage to maintain the path in code though? If we use recursion we'll get a path like "2, 7, 11, 6", so we need some little adjustments. 

You may notice that the first path is ok up to the root, then we have an inverted path. How do we handle this? There's probably multiple ways, I chose having a stack to invert the list as you can see in the code below.

Note:
- First stack is not really needed, a simple list would do - I just like symmetry.
- For the lowestCommonAncestor method see here.

5 comments:

  1. This solution does not work properly for BST. It returns extraneous nodes which are not in the path of the target nodes.

    ReplyDelete
  2. It would return duplicate nodes in path if I wanted shortest path between same nodes.

    ReplyDelete
  3. Once again, investors win or lose money based on the accuracy of the call, regardless of how much money was gained or lost.my company

    ReplyDelete
  4. I cannot wait to dig deep and kickoff utilizing resources that I received from you. Your exuberance is refreshing. BinaryStrategy.com

    ReplyDelete
  5. Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!THANKS!!!!!! recover money lost to binary options

    ReplyDelete