← Tree Traversal

Micro-Drill #216 — Kth smallest in BST (inorder)

Tree Traversal Target: 10s

Iterative inorder (sorted order for BST). Count down k, return when k reaches 0. O(H + k) time.

def kthSmallest(root, k):
    stack = []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        k -= 1
        if k == 0: return cur.val
        cur = cur.right

Type it from memory. Go.

Practice Problems

• 230. Kth Smallest Element in a BST

Related Coding Drills

• Drill #60 — Kth smallest in sorted matrix Medium
• Drill #37 — Inorder traversal Easy
• Drill #34 — BST insert Easy