Lowest Common Ancestor of a Binary Tree

MEDIUM

Description

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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 10⁵].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
p != q
p and q will exist in the tree.

Approaches

Checkout 2 different approaches to solve Lowest Common Ancestor of a Binary Tree. Click on different approaches to view the approach and algorithm in detail.

Brute Force Path Finding

Find paths from root to both nodes p and q, then compare the paths to find the last common node.

Algorithm

Create two lists to store paths from root to p and q
Use DFS to find path from root to p
Use DFS to find path from root to q
Compare both paths to find the last common node
Return the last common node as LCA

This approach involves two steps:

First, we find the path from root to both nodes p and q by doing a DFS traversal and storing the paths.
Then we compare both paths to find the last common node which will be our LCA.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path1 = new ArrayList<>();
        List<TreeNode> path2 = new ArrayList<>();
        
        findPath(root, p, path1);
        findPath(root, q, path2);
        
        TreeNode lca = null;
        int i = 0;
        while (i < path1.size() && i < path2.size()) {
            if (path1.get(i) == path2.get(i)) {
                lca = path1.get(i);
            }
            i++;
        }
        return lca;
    }
    
    private boolean findPath(TreeNode root, TreeNode node, List<TreeNode> path) {
        if (root == null) return false;
        
        path.add(root);
        if (root == node) return true;
        
        if (findPath(root.left, node, path) || findPath(root.right, node, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}

Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the tree. We need to traverse the tree twice to find paths.Space Complexity: O(H) where H is the height of the tree, needed to store the paths

Pros and Cons

Pros:

Easy to understand and implement
Works for any binary tree
No extra space needed except for storing paths

Cons:

Requires two tree traversals
Needs extra space to store paths
Not very efficient for large trees

Code Solutions

Checking out 4 solutions in different languages for Lowest Common Ancestor of a Binary Tree. Click on different languages to view the code.

/** * 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 left = lowestCommonAncestor ( root . left , p , q ); TreeNode right = lowestCommonAncestor ( root . right , p , q ); if ( left == null ) return right ; if ( right == null ) return left ; return root ; } }

Video Solution

Watch the video walkthrough for Lowest Common Ancestor of a Binary Tree

Algorithms:

Depth-First Search

Data Structures:

TreeBinary Tree

Companies:

Atlassian |Flipkart |Intuit |LinkedIn |