⚡Flashcard Drill➔
NeetCode #419LC-236MediumTrees
← Back to All Problems

#419 · #236 · Lowest Common Ancestor of a Binary Tree(二叉树的最近公共祖先)

📌 Problem Statement & Constraints

Given a binary tree and two nodes p and q, return their lowest common ancestor: the deepest node that has both as descendants (a node may be a descendant of itself). Constraints: the number of nodes is in [2, 10^5], all values are distinct, both nodes exist.

💡 Core Algorithmic Approaches

  1. Recurse bottom-up. If the current node is p or q, return it immediately -- the answer is at or above this point.
  2. Otherwise recurse into both children.
  3. If both children return a non-null result, p and q lie in different subtrees, so the current node is the LCA.
  4. If only one side is non-null, propagate it upward; that side already contains both nodes (or the LCA).

💻 Benchmark Python3 Implementation

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root is p or root is q:
            return root                    # found one of the targets, or a leaf
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root                    # p and q split here -> this is the LCA
        return left or right               # both are on one side


# Parent-pointer variant, if each node has a `parent` attribute
class Solution2:
    def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
        a, b = p, q
        while a is not b:
            a = a.parent if a.parent else q    # switch to the other chain at the top
            b = b.parent if b.parent else p
        return a

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) for the tree version, O(h) for the parent-pointer version.
💾 Space Complexity
O(h) for the recursion stack; O(1) for the parent-pointer version.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing values instead of node identity: root is p is required, since values are unique but identity is the direct test.
  • Returning as soon as one side is non-null without checking the other: both children must be examined to detect the split.
  • Assuming p and q are never ancestors of each other: the early return handles that case correctly.
  • Using the BST-specific algorithm: this tree has no ordering, so the general recursion is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems