Java Program for Least Common Ancestor Of A Binary Tree
This is common interview question. There can be a variant where we would have to find Least Common Ancestor (LCA) of a Binary Search Tree (BST). But here we will concentrate our solution for a normal unordered Binary Tree. This question is asked in companies like FaceBook, Google, Adobe, Microsoft & Amazon. You can find the problem in LeetCode or InterviewBit.
So basically we have two values B & C. And we need to find the LCA of the nodes represented by these two values. There is no guarantee that B & C exist in the tree. In case any value is missing, we should return -1 from the method.
In the tree above, 6 is the lowest common ancestor of 17 and 4.
_______10______ / \ ___6__ ___11__ / \ / \ 17 _2_ 7 8 / \ 12 4
For the solution, we will be traversing the tree twice, one for B & one for C. We will store paths to B & C separately in ArrayList variables. In case B or C is missing, that path will be empty. Once we have calculated the path, we will compare the paths & find the first element where there is a diversion or the value is equal to B or C. That will give us the LCA of the binary tree for these two values. Time complexity of this solution is O(n).
Here is a working Java code implementation of this problem.