{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Lowest Common Ancestor of a Binary Tree – Solution & Complexity

Interview solutions
/
Lowest Common Ancestor of a Binary Tree

Solution Walkthrough

1. Recognize the Pattern

The key pattern is: post-order DFS bubbles target hits upward, and the first node where left and right searches both succeed is the LCA. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O(n) — in the worst case you may visit every node once. Space: O(h) for the recursion stack, where h is the tree height (O(n) in the worst skewed case).

All 7 languages below implement the same recursive LCA traversal for a general binary tree while taking p and q as raw integer values.

def lowest_common_ancestor(root: TreeNode, p: int, q: int) -> int:
    def dfs(node: TreeNode):
        if node is None:
            return None
        if node.val == p or node.val == q:
            return node

        left = dfs(node.left)
        right = dfs(node.right)

        if left and right:
            return node
        return left if left else right

    ancestor = dfs(root)
    return ancestor.val if ancestor else 0

FAQ

See also

Practice Lowest Common Ancestor of a Binary Tree online (run code in the browser)Balanced Binary Tree solution (easy)Binary Tree Maximum Path Sum solution (hard)Diameter of Binary Tree solution (easy)Invert Binary Tree solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?