## Saturday, 1 May 2021

### 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.

``````       _______10______
/              \
___6__          ___11__
/      \        /      \
17      _2_     7        8
/   \
12    4``````
In the tree above, 6 is the lowest common ancestor of 17 and 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.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54``` ```import java.util.*; import java.lang.*; import java.io.*; //Definition for binary tree class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; left=null; right=null; } } class Solution { public int lca(TreeNode A, int B, int C) { List path1 = new ArrayList(); List path2 = new ArrayList(); TreeNode temp = A; findPathToValue(temp, path1, B); //resetting starting index temp = A; findPathToValue(temp, path2, C); if(path1.size() == 0 || path2.size() == 0){ return -1; } int smallerSize = Math.min(path1.size(), path2.size()); int i=0; for(;i path, int value){ path.add(temp.val); if(temp.val == value){ return true; } if(temp.left != null && findPathToValue(temp.left, path, value)){ return true; } if(temp.right != null && findPathToValue(temp.right, path, value)){ return true; } path.remove(path.size() - 1); return false; } } ```