Lowest Common Ancestor of a Binary Tree

Med

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

Algorithms

Depth-First Search

Data structures

Tree Binary Tree

Companies

Atlassian Flipkart Intuit LinkedIn

Prompt

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

2 approaches with complexity analysis and trade-offs.

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

Walkthrough

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.

1class Solution {2    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {3        List<TreeNode> path1 = new ArrayList<>();4        List<TreeNode> path2 = new ArrayList<>();5        6        findPath(root, p, path1);7        findPath(root, q, path2);8        9        TreeNode lca = null;10        int i = 0;11        while (i < path1.size() && i < path2.size()) {12            if (path1.get(i) == path2.get(i)) {13                lca = path1.get(i);14            }15            i++;16        }17        return lca;18    }19    20    private boolean findPath(TreeNode root, TreeNode node, List<TreeNode> path) {21        if (root == null) return false;22        23        path.add(root);24        if (root == node) return true;25        26        if (findPath(root.left, node, path) || findPath(root.right, node, path)) {27            return true;28        }29        path.remove(path.size() - 1);30        return false;31    }32}

Complexity

Time

O(N) where N is the number of nodes in the tree. We need to traverse the tree twice to find paths.

Space

O(H) where H is the height of the tree, needed to store the paths

Trade-offs

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

Use a single DFS traversal to find LCA by checking if current node is p or q and returning accordingly.

Algorithm

If root is null or equals p or q, return root
Recursively search in left subtree
Recursively search in right subtree
If both recursive calls return non-null, current node is LCA
Otherwise return the non-null value

Walkthrough

This approach uses a single DFS traversal:

If the current node is null or equals to p or q, return current node
Recursively search in left and right subtrees
If both left and right returns are non-null, current node is LCA
If one of them is null, return the non-null value

1class Solution {2    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {3        // Base case4        if (root == null || root == p || root == q) {5            return root;6        }7        8        // Search in left and right subtrees9        TreeNode left = lowestCommonAncestor(root.left, p, q);10        TreeNode right = lowestCommonAncestor(root.right, p, q);11        12        // If both left and right are non-null, we found our LCA13        if (left != null && right != null) {14            return root;15        }16        17        // Return non-null value18        return left != null ? left : right;19    }20}

Complexity

Time

O(N) where N is the number of nodes in the tree. We only need to visit each node once.

Space

O(H) where H is the height of the tree, needed for recursion stack

Trade-offs

Pros

Single pass solution
No extra space needed except recursion stack
More efficient than brute force approach
Clean and elegant solution

Cons

Recursive solution might cause stack overflow for very deep trees
Not as intuitive as the path finding approach

Solutions

Solution

1/** * 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 ; } }

1/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */ var lowestCommonAncestor =2  function (root, p, q) {3    if (!root || root == p || root == q) return root;4    const left = lowestCommonAncestor(root.left, p, q);5    const right = lowestCommonAncestor(root.right, p, q);6    if (!left) return right;7    if (!right) return left;8    return root;9  };

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode * lowestCommonAncestor ( TreeNode * root , TreeNode * p , TreeNode * q ) { if ( ! root || root == p || root == q ) return root ; TreeNode * left = lowestCommonAncestor ( root -> left , p , q ); TreeNode * right = lowestCommonAncestor ( root -> right , p , q ); if ( left && right ) return root ; return left ? left : right ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution : def lowestCommonAncestor ( self , root : 'TreeNode' , p : 'TreeNode' , q : 'TreeNode' ) -> 'TreeNode' : if root is None or root == p or root == q : return root left = self . lowestCommonAncestor ( root . left , p , q ) right = self . lowestCommonAncestor ( root . right , p , q ) return root if left and right else ( left or right ) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution ( object ): def lowestCommonAncestor ( self , root , p , q ): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if not root : return root left = self . lowestCommonAncestor ( root . left , p , q ) right = self . lowestCommonAncestor ( root . right , p , q ) if left and right : return root if root == p or root == q : return root if left : return left if right : return right return None

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem