Kth Smallest, Range Sum, and BST to Sorted Array
Leverage the sorted in-order traversal to find the kth-smallest element in O(k) and sum values within a range in O(log n + k).
Kth Smallest in a BST
Kth Smallest Element in a BST (LeetCode #230) is a classic problem that directly exploits the sorted in-order traversal. Since in-order visits nodes in ascending order, we simply count nodes as we traverse and return the value at count k. Time is O(h + k) where h is the height (to reach the leftmost node) and k is the number of steps in the in-order walk.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def kth_smallest(root, k):
count = [0]
result = [None]
def inorder(node):
if not node or result[0] is not None:
return
inorder(node.left)
count[0] += 1
if count[0] == k:
result[0] = node.val
return
inorder(node.right)
inorder(root)
return result[0]
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1)) # 1
print(kth_smallest(root, 2)) # 2Kth Smallest: Iterative with Stack
The iterative version uses the explicit-stack in-order pattern. Push left nodes until null, then pop and count. When count reaches k, return the current node's value. This avoids Python's recursion limit for very deep trees and is equally O(h + k) time and O(h) space. Interviewers often ask for the iterative version after the recursive one.
def kth_smallest_iterative(root, k):
stack = []
curr = root
count = 0
while curr or stack:
while curr: # go as far left as possible
stack.append(curr)
curr = curr.left
curr = stack.pop() # process node
count += 1
if count == k:
return curr.val
curr = curr.right # move to right subtree
return -1 # k out of range
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3)) # 3All lessons in this course
- BST Insert and Search
- BST Delete: Three Cases
- Validate BST and In-Order Properties
- Kth Smallest, Range Sum, and BST to Sorted Array