LC236 Lowest Common Ancestor of a Binary Tree 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

Postorder reports upward — the node that hears both targets from opposite sides is the LCA.

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1

Input:: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output:: 3
Explanation:: The LCA of nodes 5 and 1 is 3 — they sit on opposite sides of the root.

Example 2

Input:: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output:: 5
Explanation:: Node 5 is an ancestor of 4; a node may be a descendant of itself — answer is 5.

Constraints (ข้อจำกัด)

The number of nodes is in the range [2, 10^5].
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q and both exist in the tree.

Full solution · Try yourself firstพับไว้ด้านใน — คลิกเมื่อพร้อมดู

Bottom-up "report upward" — children signal whether they found a target.

1. Mindset Shift

If p and q sit on opposite sides of a node, that node is the meeting point = LCA.

Key insight: let both children report. Both non-null → return self. One side found → forward that side. Current node is p or q → return self immediately (covers the ancestor-of-the-other case).

2. The Logic — 4 Steps

Base — if root is None or root is p or root is q → return root
Ask left and right
If both left and right are non-null → return root (LCA)
Otherwise return the non-null side

3. LeetCode-Ready Code

Submit this on LeetCodepython

# 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":
        if root is None or root is p or root is q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        return left if left else right

4. Dry Run — p=5, q=1 on [3,5,1,...]

call	what happens	returns
root=3	not p/q · ask both sides	waiting
node=5	root is p → return 5	5
node=1	root is q → return 1	1
back at 3	left=5 and right=1	return 3 = LCA

5. Edge Cases & Pitfalls

Compare by identity (root is p), not by val — the problem passes node objects
If p is an ancestor of q: returning p immediately is correct

6. Time & Space Complexity

Time O(n) — worst case visit every node once
Space O(h) — call-stack depth

💡 Pattern summary

Postorder reporting: children signal whether they found a target; the node that hears both sides is the meeting point — useful for ancestor / intersection problems.