← all entries
A-052● Day 522026.06.28mediumleetcode #235neetcode150

Lowest Common Ancestor of a Binary Search Tree

#tree#depth-first-search#binary-search-tree#binary-tree
↗ leetcode #235 · lowest-common-ancestor-of-a-binary-search-tree
01

Problem

· problem
P.052

Lowest Common Ancestor of a Binary Search Tree

↗ leetcode #235

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. 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)."

constraints
  • · 2 ≤ number of nodes ≤ 10^5
  • · -10^9 ≤ Node.val ≤ 10^9
  • · All Node.val are unique
  • · p ≠ q and both exist in BST
// paraphrased summary — see source for full text
examples
example 1input → output
[6,2,8,0,4,7,9,null,null,3,5]
2
8
6
example 2input → output
[6,2,8,0,4,7,9,null,null,3,5]
2
4
2
example 3input → output
[2,1]
2
1
2
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What does it mean that a node can be a descendant of itself?
  • ☐
    Do we need to search for p and q in the tree first?
  • ☐
    How does the BST property help us find the LCA efficiently?
  • ☐
    What if p and q are in different subtrees of the current node?
  • ☐
    Is the time complexity always O(log n)?
  • ☐
    Is the LCA always either p or q?
  • ☐
    Should we verify the returned node is actually an ancestor of both p and q?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Begin infinite loop for traversal
○
while True:
○
for i in range(n):
○
while root is not None:
step 2· Check if both nodes are in right subtree│ nested
○
if root.val < p.val and root.val < q.val:
○
if root.val <= p.val and root.val <= q.val:
○
if root.val < p.val or root.val < q.val:
○
if p.val > root.val and q.val > root.val:
step 3· Move to right subtree│ │ nested
○
root = root.right
○
root = root.left
○
return root.right
○
root = root.right.right
step 4· Check if both nodes are in left subtree│ nested
○
elif root.val > p.val and root.val > q.val:
○
elif root.val >= p.val and root.val >= q.val:
○
elif root.val > p.val or root.val > q.val:
○
elif p.val < root.val and q.val < root.val:
step 5· Move to left subtree│ │ nested
○
root = root.left
○
root = root.right
○
return root.left
○
root = root
step 6· Return split point or ancestor node│ nested
○
else:
○
else: return None
○
else: continue
○
else: return root.left if root.left else root.right
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, x):
4
#         self.val = x
5
#         self.left = None
6
#         self.right = None
7
8
9
class Solution:
10
    def lowestCommonAncestor(
11
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
12
    ) -> "TreeNode":
13
        while True:
14
            if root.val < p.val and root.val < q.val:
15
                root = root.right
16
            elif root.val > p.val and root.val > q.val:
17
                root = root.left
18
            else:
19
                return root
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[6,2,8,0,4,7,9,null,null,3,5]
2
8
→
6
case 2
[6,2,8,0,4,7,9,null,null,3,5]
2
4
→
2
case 3
[2,1]
2
1
→
2
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.