Description
Return the kth smallest value in a BST, with valid one-based k.
Solution
def kth_smallest(root, k):
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.rightExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[3,1,4,null,2],2]- Output
2
Inorder is 1, 2, 3, 4; its second value is 2.
Example 2
- Input
[[1],1]- Output
1
Only one rank exists.
Example 3
- Input
[[2,1,3],3]- Output
3
The largest of three entries has rank three.
Approach
Iterative inorder traversal visits values in ascending order. Stop on the kth pop.
Time & space
O(h + k) time; O(h) space. Here n is the node count, and h is the tree height.