Track 06 · Ch 02 · 3 of 11230. Kth Smallest Element in a BSTMEDIUM
14:06
230MEDIUM73.5% accepted
Kth Smallest Element in a BST
Given a binary search tree and two nodes p and q in it, return their lowest common ancestor — the deepest node that has both as descendants. A node counts as a descendant of itself.
Example 1
root = [20,8,22,4,12,21,25,2,6,10,14]
p = 2, q = 6
output: 4
4 is the deepest node with both 2 and 6 below it.
Constraints
2 ≤ n ≤ 10^5−10^9 ≤ Node.val ≤ 10^9all Node.val are uniquep ≠ q, both exist in the tree
treebstdfs
not run yet
inputroot = [20,8,22,4,12,21,25,
2,6,10,14]
p = 2, q = 6
expected / yoursexpected 4yours 4
BST descent
step 2 / 5
speed1400ms
Frame 1 — at node 20
p=2 < 20 and q=6 < 20
Both on the left. Descend left.