Find the distance between 2 nodes in Binary Tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

cant the solution be simply distance of n1 and n2 …

Rohit Yadav - Feb 0, 2016

cant the solution be simply distance of n1 and n2 from lca.
dist(n1,n2)= dist(lca,n1)+dist(lca,n2)? correct me if i am wrong.

You are absolutely correct. What is being done in the above solution is, dist(n1,n2) = dist(root,n1) + dist(root,n2) - 2*dist(root,lca) as root is point of reference. Thanks.

Binary Tree  BT  kodeknight  least-common-ancestor  LCA  distance 

Find the distance between 2 nodes in Binary Tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Find the distance between two keys in a binary tree, no parent pointers are given. Distance between two nodes is the minimum number of edges to be traversed to reach one node from other. Example Dist(-4,3) = 2, Dist (-4,19) = 4 Dist(21,-4) = 3 Dist(2,-4) = 1 Solution The distance between two nodes can be obtained in terms of lowest common ancestor. Following is the formula. Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2\*Dist(root, lca) 'n1' and 'n2' are the two given keys 'root' is root of given Binary Tree. [Read More]
Binary Tree  BT  kodeknight  least-common-ancestor  LCA  distance 

First / Lowest common ancestor (LCA) of 2 node in binary tree

 Posted on January 25, 2010  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

Problem Case 1 - Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree. Case 2- What will you do if it is Binary search tree Example So for example look into below figure: So for node 4 and 14, LCA is 8. [Read More]
tree  kodeknight  least-common-ancestor  LCA  Data Structures  DS  binary-search-tree  BST  CrackingTheCodingInterview