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. VIRUS REMOVAL

    Is Your Computer Sluggish or Plagued With a Virus? – If So you Need Online Tech Repairs
    As a leader in online computer repair, Online Tech Repairs Inc has the experience to deliver professional system optimization and virus removal.Headquartered in Great Neck, New York our certified technicians have been providing online computer repair and virus removal for customers around the world since 2004.
    Our three step system is easy to use; and provides you a safe, unobtrusive, and cost effective alternative to your computer service needs. By using state-of-the-art technology our computer experts can diagnose, and repair your computer system through the internet, no matter where you are.
    Our technician will guide you through the installation of Online Tech Repair Inc secure software. This software allows your dedicated computer expert to see and operate your computer just as if he was in the room with you. That means you don't have to unplug everything and bring it to our shop, or have a stranger tramping through your home.
    From our remote location the Online Tech Repairs.com expert can handle any computer issue you want addressed, like:
    • - System Optimization
    • - How it works Software Installations or Upgrades
    • - How it works Virus Removal
    • - How it works Home Network Set-ups
    Just to name a few.
    If you are unsure of what the problem may be, that is okay. We can run a complete diagnostic on your system and fix the problems we encounter. When we are done our software is removed; leaving you with a safe, secure and properly functioning system. The whole process usually takes less than an hour. You probably couldn't even get your computer to your local repair shop that fast!
    Call us now for a FREE COMPUTER DIAGONISTIC using DISCOUNT CODE (otr214426@gmail.com) on +1-914-613-3786 or chat with us on www.onlinetechrepairs.com.







    ReplyDelete
  2. Problem: HP Printer not connecting to my laptop.

    I had an issue while connecting my 2 year old HP printer to my brother's laptop that I had borrowed for starting my own business. I used a quick google search to fix the problem but that did not help me.

    I then decided to get professional help to solve my problem. After having received many quotations from various companies, i decided to go ahead with Online Tech Repair (www.onlinetechrepairs.com).

    Reasons I chose them over the others:
    1) They were extremely friendly and patient with me during my initial discussions and responded promptly to my request.
    2) Their prices were extremely reasonable.
    3) They were ready and willing to walk me through the entire process step by step and were on call with me till i got it fixed.

    How did they do it
    1) They first asked me to state my problem clearly and asked me a few questions. This was done to detect any physical connectivity issues with the printer.
    2) After having answered this, they confirmed that the printer and the laptop were functioning correctly.
    3) They then, asked me if they could access my laptop remotely to troubleshoot the problem and fix it. I agreed.
    4) One of the tech support executives accessed my laptop and started troubleshooting.
    5) I sat back and watched as the tech support executive was navigating my laptop to spot the issue. The issue was fixed.
    6) I was told that it was due to an older version of the driver that had been installed.

    My Experience
    I loved the entire friendly conversation that took place with them. They understood my needs clearly and acted upon the solution immediately. Being a technical noob, i sometimes find it difficult to communicate with tech support teams. It was a very different experience with the guys at Online Tech Repairs. You can check out their website www.onlinetechrepairs.com or call them on 1-914-613-3786.
    Would definitely recommend this service to anyone who needs help fixing their computers.
    Thanks a ton guys. Great Job....!!

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

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

    ReplyDelete
  5. 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