Space

Open

From Fieldwork

Scales

236. Lowest Common Ancestor of a Binary Tree

leetcodetreebinary-treedfsmedium

Open pinned source

v1

The Logic: It utilizes the stack frame to bubble up the result.

If a node sees p coming from the left and q coming from the right, that node realizes, "I am the parent of both," and returns itself.
If a node receives a result from the left but None from the right, it simply passes the left result up the chain.

Handling Descendants: This naturally handles the edge case where one node is a direct ancestor of the other (e.g., p is the parent of q). Because of the base case if root == p, the function stops traversing down at p and returns it immediately, effectively identifying p as the LCA.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Base Case:
        # 1. If the tree is empty, return None.
        # 2. If we found either p or q, return that node.
        if not root or root == p or root == q:
            return root

        # Recursive Step: Look for p and q in the left and right subtrees
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        # Logic:
        # If both left and right returned a node, it means p is in one side 
        # and q is in the other. Therefore, the current 'root' is the split point (LCA).
        if left and right:
            return root
        
        # If only one side returned a node, it means both p and q are in that specific subtree 
        # (or one is inside the other). Return the non-None side.
        return left or right

Practice bench

Continue the thread

A private scratchpad for this reading. Nothing is sent or scored.

You

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode