Developers Nest - Intensify Your Coding Skills

The least Common Ancestor is one of those problems which appear quite complicated, but is pretty straightforward and can be solved easily.  So in this blog, we're going to understand how to find LCA in a BST & a Binary Tree. Given a binary tree and two nodes n1=1 & n2=4, so the first common node for n1 & n2 with the minimum difference in their heights is 3, therefore 3 is the LCA for n1 & n2. Let's discuss where cases to make you understand LCA better: For n1 = 2, n2 = 3  LCA=> 3 For n1 = 4, n2 = 8  LCA=> 5 For n1 = 7, n2 = 9  LCA=> 8 So now let's try to find LCA in a Binary Search Tree: In a binary search tree, the elements to the left of the root are smaller than the root, and elements to the right of the root are greater than the root. We can find the LCA according to the following conditions : Both n1 & n2 are smaller than the root so, LCA will be in the left sub-tree. Both n1 & n2 are greater than the root so, LCA will be in the ...