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<Integer> path1 = new ArrayList<Integer>();
        List<Integer> path2 = new ArrayList<Integer>();
        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<smallerSize; i++){
            if(!path1.get(i).equals(path2.get(i))){
                break;
            }
        }
        return path1.get(i - 1);
    }
    
    private boolean findPathToValue(TreeNode temp, List<Integer> 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;
    }
}

Comments