Lowest Common Ancestor of a Binary Tree

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

_______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Approach

Below are 2 different approaches to solve this problem:

Method1

• Find the paths from root to nodeP and root to nodeQ
• Compare both paths to return the Lowest Common Ancestor which is the node before the first mismatch.
• Lets consider the above example with node 5 and node 1:
• Path from root to 5 = {3,5}
• Path from root to 1 = {3,1}
• The node before the first mismatch is 3

Run Time Complexity

The run time for recursive function isChild() is O(n) and lowestCommonAncestor() is O(n). Now since isChild() is called inside lowestCommonAncestor() so overall run time complexity is O(N2).

which can be derived from the following recurrence relation:

T(n) = 2T(n/2) + 1 — — — — — — — — — — — -1

Using substitution method:

T(n/2) = 2T(n/4)+1 — — — — — — — — — — — -2

Substituting the value of T(n/2) in eqn 1

T(n) = 4T(n/4) + 3 — — — — — — — — — — — — 3

Now we again substitute n for n/4

T(n/4) = 2T(n/8) + 1 — — — — — — — — — — — 4

Substituting the value of T(n/4) in eqn 3

T(n) = 8T(n/8)+7 — — — — — — — — — — — — — -5

Equation 5 can be written as:

T(n) =2k T(n/2k) +7

If, n/2k = 1 => k = log n base 2

T(n) = n + 7 , since 2log n = n and T(1) = 1

so running time is O(n)

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }if((p == root) || (q == root)){
            return root;
        } 
        if(root.left == null && root.right == null){
            return null;
        }
        List<TreeNode> path1 = new ArrayList<>();
        List<TreeNode> path2 = new ArrayList<>();
        
            path1 = getPath(root,p,path1);
            path2 = getPath(root,q,path2);
        if(path1.size() > 1 &&  path2.size() > 1){
            for(int i = 0; i < path1.size(); i++){
                if((i == path1.size()-1 || i == path2.size()-1) && path1.get(i) == path2.get(i)){
                    return path1.get(i);
                }
                if(path1.get(i) != path2.get(i)){
                    return path1.get(i-1);
                }
            }
        }
        return null;
}
    /**
     * Return the path from root to node
     */
    private  List<TreeNode> getPath(TreeNode root, TreeNode node, List<TreeNode> path){
            if(root == null){
            return path;
            }
            if(root == node){
                path.add(root);
                return path;
            }
            if(root.left == node){
                path.add(root);
                path.add(root.left);
                return path;
            }
            if(root.right == node){
                path.add(root);
                path.add(root.right);
                return path;
            }
            if(isLeftChild(root,node)){
                path.add(root);
                return getPath(root.left,node,path);
            }else{
                path.add(root);
                return getPath(root.right,node,path);
            }
    }
/**
     * Return true if the a given node is in the left subtree
    */
    private boolean isLeftChild(TreeNode root, TreeNode node){
        return isChild(root.left,node);
    }
    
    /**
     * Return true if the a given node is in the right subtree
    */
    private boolean isRightChild(TreeNode root, TreeNode node){
         return isChild(root.right,node);   
    }
    
    /**
     * Return true if the a given node is a child of the tree rooted at parent.
    */
    private boolean isChild(TreeNode parent, TreeNode child){
        if(parent == null){
            return false;}
        if(parent == child){
            return true;
        }return (isChild(parent.left,child) || isChild(parent.right,child));
    }
}
Method2

• This is a bottom up approach where the base case is
• If the root is null then return null.
• If the one of the nodes(p or q) is root, then return root.
• Now we find the left node and the right node by recursively calling lowestCommonAncestor on left, right subtrees and check if :
• Both left and right are not null, then root is the lowest common ancestor.
• If left is null then both the nodes are in right subtree and the right node is the LCA.
• If right is null then both nodes are in the left subtree and the left node is the LCA

Run Time Complexity

The complexity for this approach is O(n).
The recurrence for the below code is:
T(n) = 2T(n/2) + 1 .
Using the substitution method described above we can conclude the time is O(n)
Code
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }if((p == root) || (q == root)){
            return root;
        } 
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null){
            return root;
        }
        TreeNode ancestor = ((left == null) ? right : left);
        return ancestor;
    }
}