Lowest Common Ancestor of a Binary Tree Solution Explained

Data Structures / Tree

Lowest Common Ancestor of a Binary Tree

Medium

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


Tree:
        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

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.

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.

Explanation

The Lowest Common Ancestor (LCA) is the deepest node that has both target nodes as descendants. Think of it as the first meeting point when climbing up the tree from both nodes.

We use a recursive approach that leverages the tree structure:

If the current node is null, return null (base case)
If the current node equals p or q, return the current node (found one target)
Recursively search the left and right subtrees
If both subtrees return non-null, current node is the LCA
If only one subtree returns non-null, propagate that result upward

The key insight is that once we find both p and q in different subtrees of a node, that node must be their lowest common ancestor!

Idea Map

Start at Root

Is current node null, p, or q?

Yes → Return current

No → Recurse left & right

Left result: left
Right result: right

• Both non-null? → Current is LCA
• One non-null? → Return that one
• Both null? → Return null

Return LCA

Complexity Analysis

Time Complexity

O(n) - In the worst case, we visit every node in the tree once during the traversal.

Space Complexity

O(h) - where h is the height of the tree, due to the recursion stack. O(n) in worst case for skewed trees, O(log n) for balanced trees.

Code


def lowestCommonAncestor(root, p, q):
Function takes the root of the tree and two target nodes p and q to find their LCA.
    # Base case: if root is None or matches p or q
Comment explaining the base case conditions.
    if not root or root == p or root == q:
If current node is null (empty subtree) or equals p or q, return it. A node is its own ancestor.
        return root
Return the found node (could be p, q, or null).
    # Recursively search left and right subtrees
Comment explaining the recursive search.
    left = lowestCommonAncestor(root.left, p, q)
Recursively search for p or q in the left subtree. Returns the found node or null.
    right = lowestCommonAncestor(root.right, p, q)
Recursively search for p or q in the right subtree. Returns the found node or null.
    # If both sides found something, current node is LCA
Comment explaining the LCA detection logic.
    if left and right:
If both left and right returned non-null, p and q are in different subtrees. Current node is their LCA!
        return root
Return current node as the LCA since both targets were found in different subtrees.
    # Otherwise, return whichever side found something
Comment explaining the propagation logic.
    return left if left else right
Propagate the non-null result upward. If both are null, returns null. This bubbles up found nodes to ancestors.


public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Function takes the root of the tree and two target nodes p and q to find their LCA.
    // Base case: if root is null or matches p or q
Comment explaining the base case conditions.
    if (root == null || root == p || root == q) {
If current node is null (empty subtree) or equals p or q, return it. A node is its own ancestor.
        return root;
Return the found node (could be p, q, or null).
    }
End of base case if statement.
    // Recursively search left and right subtrees
Comment explaining the recursive search.
    TreeNode left = lowestCommonAncestor(root.left, p, q);
Recursively search for p or q in the left subtree. Returns the found node or null.
    TreeNode right = lowestCommonAncestor(root.right, p, q);
Recursively search for p or q in the right subtree. Returns the found node or null.
    // If both sides found something, current node is LCA
Comment explaining the LCA detection logic.
    if (left != null && right != null) {
If both left and right returned non-null, p and q are in different subtrees. Current node is their LCA!
        return root;
Return current node as the LCA since both targets were found in different subtrees.
    }
End of LCA detection if statement.
    // Otherwise, return whichever side found something
Comment explaining the propagation logic.
    return left != null ? left : right;
Propagate the non-null result upward. If both are null, returns null. This bubbles up found nodes to ancestors.
}
End of the function.


TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
Function takes the root of the tree and two target nodes p and q to find their LCA.
    // Base case: if root is null or matches p or q
Comment explaining the base case conditions.
    if (root == nullptr || root == p || root == q) {
If current node is null (empty subtree) or equals p or q, return it. A node is its own ancestor.
        return root;
Return the found node (could be p, q, or null).
    }
End of base case if statement.
    // Recursively search left and right subtrees
Comment explaining the recursive search.
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
Recursively search for p or q in the left subtree. Returns the found node or null.
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
Recursively search for p or q in the right subtree. Returns the found node or null.
    // If both sides found something, current node is LCA
Comment explaining the LCA detection logic.
    if (left != nullptr && right != nullptr) {
If both left and right returned non-null, p and q are in different subtrees. Current node is their LCA!
        return root;
Return current node as the LCA since both targets were found in different subtrees.
    }
End of LCA detection if statement.
    // Otherwise, return whichever side found something
Comment explaining the propagation logic.
    return left != nullptr ? left : right;
Propagate the non-null result upward. If both are null, returns null. This bubbles up found nodes to ancestors.
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Node can be its own ancestor

Remember that a node is considered a descendant of itself. If p is an ancestor of q (or vice versa), p (or q) is the LCA, not p's parent.

💡

Both nodes are guaranteed to exist

The problem guarantees both p and q exist in the tree, so we don't need to handle the case where one or both nodes are missing.

✓

Compare by reference, not value

When checking if current node equals p or q, compare by object reference (==), not by value. Two different nodes might have the same value.

Deepen Your Understanding

The Lowest Common Ancestor problem is a classic tree algorithm that combines recursion with clever propagation logic. Understanding how information flows up the tree is key to mastering tree algorithms.

Learn more about tree algorithms →

park

Disclaimer: This problem is for educational purposes. Practice the 'Lowest Common Ancestor of a Binary Tree' problem on LeetCode.

AlgoExplained.dev