Domain 2MediumCORE

Lowest Common Ancestor of a Binary Tree

We are given the root of a binary tree and two specific nodes, p and q, which we know exist within that tree. Our goal is to identify the Lowest Common Ancestor (LCA) node.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree

236. Lowest Common Ancestor of a Binary Tree

Model: qwen3.5:9b
Topics: Tree
FAANG asked: 1
Acceptance rate: 49.3%


Problem Breakdown

We are given the root of a binary tree and two specific nodes, p and q, which we know exist within that tree. Our goal is to identify the Lowest Common Ancestor (LCA) node.

According to the definition provided: The LCA must be the deepest node in the tree such that both p and q are descendants of it. Crucially, a node can be its own descendant. This means if one target (p) is an ancestor of the other (q), then p itself is the answer.

Inputs:

  • A binary tree root (TreeNode).
  • Two TreeNode references: p, q.

Outputs:

  • The TreeNode representing the LCA.

Constraints & Edge Cases to Consider:

  1. Tree Structure: It’s a general Binary Tree, not necessarily balanced or a BST. We cannot rely on value comparisons for traversal direction (unlike LC235).
  2. Node Existence: p and q are guaranteed to exist in the tree; we don’t need error handling for missing nodes.
  3. Uniqueness: All node values (val) are unique, so identity checks can rely on value or reference equality without ambiguity.
  4. Ancestor Rule: A common pitfall is forgetting that a node counts as its own descendant (Example 2).

Intuition

Let’s think about how we traverse the tree to find p and q.

A brute-force approach would be to perform two separate traversals: one from root to p and another from root to q, storing their paths, then finding the last common node in those lists. However, this requires explicit storage for parent pointers or path tracking (O(N)O(N) space) because we don’t know which direction leads to a target until we reach it (since it’s not a BST).

A more efficient insight comes from thinking about what information needs to bubble up during traversal. If I am at any node curr in the tree:

  1. If curr is either p or q: This node must be part of the path for itself and potentially its descendants. We return this node immediately upwards because it satisfies the “descendant” condition (including self).
  2. Recurse Left: Ask if we find a target in the left subtree. Let’s say result is left.
  3. Recurse Right: Ask if we find a target in the right subtree. Result is right.

Now, analyze what happens when results come back:

  • If both left and right are non-null (valid nodes found), it means one target was on the left branch and the other was on the right branch. Therefore, the current node must be their lowest common ancestor because they split here. We return curr.
  • If only one side returns a valid node (left != None or right != None) but not both: The target found is in that subtree and we haven’t reached the LCA yet (or this node IS an ancestor). We simply propagate that result up to our parent.
  • If neither side finds anything, return null.

This post-order traversal logic allows us to solve it without explicit path storage, relying on the recursion stack implicitly.

Approach

We will implement a recursive Depth First Search (DFS) function dfs(node) that returns either:

  1. The LCA node if found in this subtree.
  2. One of the target nodes (p or q) if we hit it directly and haven’t seen both yet.
  3. None if neither is present in this branch (though given constraints, one will always be found eventually).

Algorithm Steps:

  1. Base Case: If node is null, return None.
  2. Match Check: If the current node equals either p or q, we stop descending and return this node immediately to signal “found”. This handles the case where one target is an ancestor of another.
  3. Recursive Calls: Call dfs(node.left) and dfs(node.right).
  4. Result Aggregation:
    • If both left and right calls returned non-null values, we found a split point here. Return current node (node).
    • Otherwise (if only one side is valid), return that single result to propagate up the tree chain until it hits an ancestor or another target match.

Complexity Analysis

  • Time Complexity: O(N)O(N) where N is the number of nodes in the binary tree. In the worst case, we visit every node exactly once because each recursive call processes a subtree and returns immediately upon finding targets. We do not backtrack to search again for p or q.
  • Space Complexity: O(H)O(H) where H is the height of the tree due to recursion stack usage. In an unbalanced (skewed) tree, this degrades to O(N)O(N). For a balanced binary tree, it remains O(log⁡N)O(\log N).

Solution

# 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':
        
        # Base case: if node is null or matches target, return it.
        # Returning the matched node immediately handles the "ancestor of itself" rule naturally.
        if not root or root == p or root == q:
            return root
        
        # Recursively search in left and right subtrees
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        # If both sides returned a valid node (not None), it means 
        # one target was found on the left path and another on the right.
        # Thus, current root is the LCA.
        if left and right:
            return root
        
        # Otherwise, propagate whichever side found a match up to the parent stack frame.
        # If only 'left' returned something (or vice versa), that node 
        # continues being the candidate for LCA as we go higher.
        return left or right

Edge Cases Handled

  • One target is ancestor of another: The code returns root immediately if it matches a target (p == root). If recursion finds one child and not the other, that result bubbles up to this node (or its ancestors). Example 2 logic holds.
  • Root is LCA: Both recursive calls return valid nodes; condition if left and right: triggers at root level.
  • Skewed Tree / Deep Recursion: The recursion depth matches tree height, handled by Python’s stack limit constraints (though 10510^5 might hit limits in some environments without tail-call optimization or iterative conversion). For this problem context, recursive solution is standard and accepted within typical interview time/space bounds.
  • Single Node Tree / Two Nodes: Constraints say nodes range [2, 10^5], so single node tree isn’t possible per constraints (min 2), but logic holds regardless of size.