0236.Lowest Common Ancestor of BT

Link: 236. Lowest Common Ancestor of a Binary Tree - Medium
Track: NeetCode150

Question

Restate the problem

• Given a tree, two node p, q
• Return Node
• Find the LCA in binary tree

p and q are guaranteed to exist
LCA: the lowest node in the three has both p and q in its subtree, A node can be an ancestor of itself.

---

Method 1
Method 2

Method - DFS(postorder)

Approach

Invariant: dfs(node)

• returns None if neither target exists in this subtree;
• returns p or q if exactly one exists;
• returns the LCA if both exist.

Base case: if not node, return None
If node p or node q: return node
Recurse: search left and right
If both found: return node (the node is LCA)

• else return whichever side is non-null
  • if left and right: return node
  • else return left if left else right

Complexity

• Time Complexity: O(n)
• Space Complexity: O(h)
  • balanced O(logn)
  • worst O(n)

Edge Case

• No root

Code

# 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':
        def dfs(node, p, q):
            if not node:
                return None
            
            if node == p or node == q:
                return node
 
            left = dfs(node.left, p, q)
            right = dfs(node.right, p, q)
 
            if left and right:
                return node
            
            if left:
                return left
            if right:
                return right
        
        return dfs(root, p, q)

---

History

Jan-19-2026 Solved w bug, bad explanation