Kth Smallest Element in a BST
MediumThe problem
Given a binary search tree and a number k, return the k-th smallest value stored in the tree, counting from 1.
- Example 1Input: root = [3, 1, 4, null, 2], k = 1Output: 1
- Example 2Input: root = [5, 3, 6, 2, 4, null, null, 1], k = 3Output: 3
Sorted, the values are 1, 2, 3, 4, 5, 6, and the 3rd is 3.
Limits
- 1 ≤ k ≤ number of nodes ≤ 10,000
- 0 ≤ node value ≤ 10,000
- All values are different
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
What traversal order of a BST visits values from smallest to largest?
The idea
Inorder traversal (left, node, right), counting visited nodes; stop at the k-th.
Target: O(h + k) time
Go function shape
func kthSmallest(root *TreeNode, k int) intReference solution
Tested with go test. Try it yourself first, then compare.
// KthSmallest: an inorder walk (left, node, right) of a BST visits values in increasing order,
// so stop at the k-th visited node.
func KthSmallest(root *TreeNode, k int) int {
var stack []*TreeNode
cur := root
for cur != nil || len(stack) > 0 {
for cur != nil {
stack = append(stack, cur) // go as far left as possible
cur = cur.Left
}
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if k--; k == 0 {
return cur.Val
}
cur = cur.Right
}
return -1
}