{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Lowest Common Ancestor of a Binary Tree – Solution & Complexity

Interview solutions
/
Lowest Common Ancestor of a Binary Tree

Solution Walkthrough

  1. Step 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. Step 2: Build the Algorithm

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

  3. Step 3: Check Edge Cases

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

  4. Step 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 Inorder Traversal solution (easy)Binary Tree Maximum Path Sum solution (hard)Binary Tree Postorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?