DSA sheet · Trees · Binary Search Tree pattern

Kth Smallest in a BST

Find the k-th smallest value in a binary search tree. The teacher builds up three answers: first one that would work for any binary tree (collect + sort), then one that uses the fact that inorder of a BST is already sorted, and finally the optimised one: walk the inorder with a stack, one value at a time, and stop the moment you've counted k values. That last idea is the same machine as BST Iterator. Her general tip: when a question says "BST" and asks about "smallest" or "largest", there is almost always a sorted-order trick waiting to be used.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: collect everything and sort
• Part B · Better: inorder gives sorted order for free
• Part C · Optimal: stack-based inorder that stops at k
• Part D · Revision page

Part 0 · Before starting

Tree node

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # the number in this node
        self.left = left     # left child, or None
        self.right = right   # right child, or None

The BST property

A Binary Search Tree promises, at every node: all values in the left subtree (the left child and everything under it) are smaller than the node, and all values in the right subtree are bigger. This holds for every node below, not just the direct children. In the tree below, 4 is the right child of 3 (bigger than 3 ✓) but it also lives inside 5's left subtree, so it must be smaller than 5 ✓. And 6 is the left child of 7, but it is in 8's left subtree and 5's right subtree, so it must be between 5 and 8 ✓.

            5
          /   \
         3     8
        / \   / \
       2   4 7   9
      /     /
     1     6

The teacher's tree for this video (values 1 to 9).

Why inorder of a BST is sorted

Inorder = visit the left subtree, then the node, then the right subtree, with the same rule inside every subtree. At each node the left side holds only smaller values and the right side only bigger ones. So inorder always lists "smaller ones, me, bigger ones", and doing that at every level gives the whole tree in increasing order. For the tree above: 1 2 3 4 5 6 7 8 9.

Stack

A stack is a pile: append puts on top, pop takes from the top. The last thing in is the first thing out. In Python a list works as a stack.

Part A · Brute force: collect everything and sort

LeetCode 230 · Kth Smallest Element in a BST

1The question in simple words

You get the root of a BST and a number k. Return the k-th smallest value. k counts from 1: k = 1 means the smallest, k = 2 the second smallest, and so on.

• Teacher's tree, k = 1 → 1; k = 2 → 2; k = 4 → 4; k = 9 → 9.
• LeetCode example: tree [3, 1, 4, null, 2] (3 on top, 1 on its left, 4 on its right, 2 as 1's right child), k = 1 → 1.

2What the constraints tell us

• 1 ≤ k ≤ n ≤ 10⁴, where n is the number of nodes. So k is always valid: with 10 nodes you could be asked for the 1st, 2nd, … up to the 10th smallest, never the 11th. And the tree is never empty.
• Values: 0 to 10⁴ → fits in a normal int (up to about 2·10⁹). We don't add or multiply values anyway, we just return one, so there's no need for a bigger type like long.
• n ≤ 10⁴ is small, so even O(n log n) passes easily. The later parts are about doing less work and using less memory.

3Intuition

The teacher says: forget the BST property for a moment. Pretend it's just a plain binary tree. How would you find the k-th smallest? Visit every node in any order (preorder, inorder, postorder, it doesn't matter), write all the values in a list, sort the list, and pick position k − 1.

4Building the logic

Visiting the teacher's tree might give the list [5, 3, 2, 1, 4, 8, 7, 6, 9] (preorder). After sorting: [1, 2, 3, 4, 5, 6, 7, 8, 9].

• k = 1 → index 0 → 1. k = 2 → index 1 → 2.

5Approach steps

1. Traverse the tree (any order) and append every value to a list.
2. Sort the list.
3. Return list[k - 1].

6Code (Python)

class Solution:
    def kthSmallest(self, root, k):
        vals = []

        def visit(node):                 # preorder; any order works here
            if node is None:
                return
            vals.append(node.val)
            visit(node.left)
            visit(node.right)

        visit(root)
        vals.sort()
        return vals[k - 1]

7Code line by line

8Dry run

1. Collect (preorder): [5, 3, 2, 1, 4, 8, 7, 6, 9].
2. Sort: [1, 2, 3, 4, 5, 6, 7, 8, 9].
3. k = 4 → index 3 → 4.

9Complexity & remember

• Time O(n log n): O(n) to collect, then O(n log n) to sort. The sort is the bigger part, so the total is O(n log n).
• Space O(n): every value is stored.

The teacher's point: this ignores the one thing the question handed us. It says BST, and a BST is related to sorted order. Whenever you see that, don't stop at this approach.

Part B · Better: inorder gives sorted order for free

1The question (same)

k-th smallest value in a BST.

2Constraints

Same as Part A.

3Intuition

Of the three traversals (preorder, inorder, postorder), inorder is special for a BST: it visits values in sorted order already (see Part 0). So if we collect with inorder instead of preorder, the list is sorted without calling sort. That removes the n log n step.

4Building the logic

Inorder of the teacher's tree: go left from 5 to 3 to 2 to 1. Write 1, then 2, then 3, then 3's right child 4, then 5, then 5's right subtree: 6, 7, 8, 9. So the list is [1, 2, 3, 4, 5, 6, 7, 8, 9], sorted straight away. Answer = list[k - 1].

5Approach steps

1. Do an inorder traversal and append each value to a list.
2. Return list[k - 1].

6Code (Python)

class Solution:
    def kthSmallest(self, root, k):
        vals = []

        def inorder(node):
            if node is None:
                return
            inorder(node.left)           # smaller values first
            vals.append(node.val)
            inorder(node.right)          # bigger values after

        inorder(root)                    # vals is sorted already
        return vals[k - 1]

7Code line by line

8Dry run

1. inorder fills [1, 2, 3, 4, 5, 6, 7, 8, 9].
2. k = 4 → index 3 → 4. k = 9 → index 8 → 9.

9Complexity & remember

• Time O(n): just one traversal, no sort. Far better than O(n log n).
• Space O(n): the list (plus the recursion stack).

Part C · Optimal: stack-based inorder that stops at k

1The question (same)

k-th smallest value in a BST, now without storing every value and without visiting more than we need.

2Constraints

Same. We aim for about O(h + k) time and O(h) space, where h is the height of the tree (the number of levels on the longest path from the root down to a leaf).

3Intuition

We only need the first k values of the inorder order, so let's produce inorder values one at a time, keep a countdown, and stop as soon as it hits 0. Producing inorder values one at a time is exactly what we learnt in BST Iterator:

• We only have the root. The smallest value is the leftmost node, so walk left from the root and push every node on the way onto a stack: 5, 3, 2, 1.
• Pop the top: it's the smallest not-yet-counted value. Count it (k goes down by 1).
• Before moving on, if the popped node has a right child, go there and again push it and all its lefts. Those values are smaller than everything still below on the stack, so they must come out next.

4Building the logic from examples

k = 1

Stack after walking left: [5, 3, 2, 1]. Pop 1, k becomes 0. k hit 0, so 1 is the answer. We touched only 4 nodes.

k = 2

Pop 1 → k = 1 (1 has no right child, push nothing). Pop 2 → k = 0 → answer is the value just popped: 2.

k = 3

One more pop gives 3 → answer 3.

k = 4: the trap

The teacher stops here and asks: with the stack [5, 3, 2, 1], after popping 1, 2, 3, is the 4th pop going to be 5? No! The 4th smallest is 4. The fix is the BST Iterator rule: after every pop, check whether the node has a right child. 3 has a right child, 4. Anything in 3's right subtree is bigger than 3 but still smaller than 3's parent 5. So when we pop 3, we must push 4 (and 4's left chain, which is empty) before anything else. Then the next pop is 4 ✓.

• Pop 1: k 4 → 3. No right child.
• Pop 2: k → 2. No right child.
• Pop 3: k → 1. Right child 4 → push it.
• Pop 4: k → 0 → the answer is 4 ✓

Writing it as one loop

The teacher writes this with one pointer, cur (she reuses the name root for it), and two loops:

• An inner loop that pushes cur and keeps going left until cur is None. That pushes a whole left chain at once.
• Then pop a node, decrease k, and if k is 0 return its value.
• Then set cur = node.right. If there is a right child, the inner loop will push its left chain on the next round. If not, cur is None and the inner loop does nothing.

The outer loop condition: while cur is not None or stack

Why not simply "while the stack is not empty"? The teacher shows two moments where that would go wrong:

1. Stack empty, but cur is not None. In the full walk of her tree: after popping 1, 2, 3, 4, we pop 5. Now the stack is empty! But 5 has a right child, so cur = 8. The whole right half (6, 7, 8, 9) hasn't been visited. If the loop only checked the stack, it would stop here, wrongly.
2. cur is None, but the stack is not empty. In the LeetCode example [3, 1, 4, null, 2]: push 3, 1; pop 1; go to its right child 2; push 2; pop 2; 2 has no right child, so cur becomes None. But 3 and its right side are still waiting on the stack. If the loop only checked cur, it would stop too early.

So we keep going while either one still has work: a node to dive into (cur) or nodes waiting on the stack. We stop only when both are finished: cur is None and the stack is empty. That means the whole tree is done.

5Approach steps

1. Make an empty stack. Set cur = root.
2. While cur is not None or the stack is not empty:
3.   while cur is not None: push it, cur = cur.left.
4.   Pop a node. Decrease k by 1. If k is 0, return node.val.
5.   cur = node.right.
6. After the loop, return −1 (never reached when k is valid).

6Code (Python)

class Solution:
    def kthSmallest(self, root, k):
        stack = []
        cur = root
        while cur is not None or stack:
            while cur is not None:       # push the whole left chain
                stack.append(cur)
                cur = cur.left
            node = stack.pop()           # next value in sorted order
            k -= 1
            if k == 0:
                return node.val          # this is the k-th smallest
            cur = node.right             # its right subtree comes next
        return -1                        # not reached when 1 <= k <= n

7Code line by line

8Dry run: watch the stack

Left of each stack picture = bottom, red = top.

            5
          /   \
         3     8
        / \   / \
       2   4 7   9
      /     /
     1     6

Run 1: k = 4 (the teacher's main example)

1. cur = 5. Inner loop pushes 5, 3, 2, 1, then cur = 1.left = None.

1. Pop 1 → k = 3. Not 0. cur = 1.right = None.

1. Loop again (stack not empty). Inner loop skips (cur is None). Pop 2 → k = 2. cur = 2.right = None.

1. Pop 3 → k = 1. cur = 3.right = 4.

1. Inner loop pushes 4 (4 has no left child, so it stops there).

1. Pop 4 → k = 0 → return 4 ✓. We never touched the right half of the tree.

Run 2: k = 9 (the full walk, which shows why the loop needs "or")

Steps 1 to 5 of Run 1 happen again: pops 1, 2, 3, 4 (k goes 9 → 8 → 7 → 6 → 5). After popping 4, cur = 4.right = None.

1. Pop 5 → k = 4. cur = 5.right = 8. The stack is empty now, but cur is not None, so the outer loop keeps going.

1. Inner loop pushes 8, 7, 6 (8 → left 7 → left 6 → left None).

1. Pop 6 → k = 3. 6 has no right child → cur = None.

1. Pop 7 → k = 2. No right child → cur = None.

1. Pop 8 → k = 1. cur = 8.right = 9. Stack empty again, but cur exists → keep going.

1. Inner loop pushes 9.

1. Pop 9 → k = 0 → return 9 ✓. (If k had been larger than n, we'd set cur = 9.right = None with an empty stack. Both are finished, so the loop would end.)

Run 3: LeetCode example [3, 1, 4, null, 2], k = 3

      3
     / \
    1   4
     \
      2

1. Push 3, 1. Pop 1 → k = 2. cur = 1.right = 2.

1. Push 2. Pop 2 → k = 1. cur = 2.right = None.

1. cur is None, but the stack still holds 3 → the loop continues. Pop 3 → k = 0 → return 3 ✓ (sorted order is 1, 2, 3, 4).

9Complexity & remember

• Time O(h + k). The first left walk costs about h pushes, even for k = 1. After that, each counted value costs a pop plus a few pushes. The teacher sums it up as "whichever is bigger of log n and k". For k = 1 or 2 it's about the height; for k = 9 in her tree it's about k pops (here every node, so about n). Either way we stop at k instead of always visiting all n.
• Space O(h). The stack holds at most one node per level, because by the time we go into a right part, the left part's nodes have already been popped.

Part D · Revision page

root = TreeNode(5,
                TreeNode(3, TreeNode(2, TreeNode(1)), TreeNode(4)),
                TreeNode(8, TreeNode(7, TreeNode(6)), TreeNode(9)))
s = Solution()
print([s.kthSmallest(root, k) for k in range(1, 10)])   # [1, 2, 3, 4, 5, 6, 7, 8, 9]
ex = TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4))
print(s.kthSmallest(ex, 1), s.kthSmallest(ex, 3))        # 1 3

Based on this video: Kth Smallest Element in a BST