⚡Flashcard Drill➔
NeetCode #420LC-1650MediumTrees
← Back to All Problems

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

📌 Problem Statement & Constraints

Given two nodes p and q in a binary tree where each node has a parent pointer, return their lowest common ancestor. Constraints: the number of nodes is in [2, 10^5], all values are distinct.

💡 Core Algorithmic Approaches

  1. With parent pointers, the problem is identical to finding the intersection of two singly linked lists.
  2. Advance both pointers one step at a time; when one reaches the top (its parent is None), redirect it to the other node.
  3. After at most depth(p) + depth(q) steps, both pointers have travelled the same total distance and meet at the LCA.
  4. This needs no depth computation and uses O(1) space.

💻 Benchmark Python3 Implementation

class Solution:
    def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
        a, b = p, q
        while a is not b:
            # when a chain ends, continue along the other chain
            a = a.parent if a.parent else q
            b = b.parent if b.parent else p
        return a

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(depth(p) + depth(q)): both pointers travel the combined path length.
💾 Space Complexity
O(1): two pointers.

⚠️ Interview Pitfalls & Follow-ups

  • Not switching chains at the root: the pointers would simply reach None and never meet.
  • Computing the depths and aligning the pointers: correct and O(1) space, but the chain-switching trick is shorter.
  • Using a set of visited ancestors: O(h) space for the same result.
  • Assuming the nodes are at the same depth: they need not be, which is exactly what the switching equalises.
⚡
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