Find the distance between given pairs of nodes in a binary tree

Given a binary tree, determine the distance between given pairs of nodes in it. Distance between two nodes is defined as the number of edges in shortest path from one node from other.


 

For example, consider below binary tree. The distance between node 7 and node 6 is 3.

 
distance-between-two-nodes

 


 

This problem is a standard application of lowest common ancestor of given nodes. The distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor.

C++

Download   Run Complete Code

 
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of