Java: Lowest Common Ancestor of a Binary Tree

Thought Process

To find the lowest common ancestor of two nodes (say 'p' & 'q') in a binary tree, we can use a recursive approach. If the current node is NULL or matches either 'p' or 'q', it is a potential LCA. Otherwise, we recursively search for 'p' and 'q' in the left & right subtrees. If both subtrees return non-null results, then the current node is LCA. Otherwise, we return the non-null result from either subtree. 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        if(root == null || root == p || root == q)
            return root;
        
        TreeNode srchInLeftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode srchInRightTree = lowestCommonAncestor(root.right,p,q);

        if(srchInLeftTree!=null && srchInRightTree!=null)
            return root;
        else if(srchInLeftTree==null && srchInRightTree!=null)
            return srchInRightTree;
        else if(srchInLeftTree!=null && srchInRightTree==null)
            return srchInLeftTree;
        else
            return null;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree (h). In the worst case, the space complexity is O(n).

Code copied!