BSTs, iterative DFS & recursion depth

Trees: DFS & BFS, lesson 3 of 3

BSTs, iterative DFS & recursion depth

Use the BST ordering to skip half the tree, and traverse with your own stack when recursion gets deep.

12 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

A binary search tree (BST) keeps its values ordered: for every node, everything in its left subtree is smaller and everything in its right subtree is larger.

        8
       / \
      3   10
     / \    \
    1   6    14

Two consequences to remember:

  • Search / insert only ever go one way at each node, so they cost O(h): O(log n) when balanced, O(n) for a degenerate chain.
  • An in-order traversal visits the values in sorted order.
Example

Search, insert, and in-order = sorted

insert returns the (possibly new) subtree root, so the parent can reattach it: a neat pattern for any function that changes tree shape.

Quiz

Is this a valid BST?

Iterative DFS with a stack. Recursion uses the call stack; you can manage your own list instead.

  • Pre-order: pop a node, visit it, push its right child first, then its left, so the left comes off the stack next.
  • In-order: walk left pushing every node; when you can't go further, pop, visit, then step into the right child.

Iterative in-order is the go-to for "k-th smallest in a BST": stop as soon as you've visited k nodes.

Example

Iterative pre-order and in-order

Same O(n) time and O(h) space as recursion, but no recursion limit. BFS is this exact loop with a queue instead of a stack.

Quiz

This version pushes the left child before the right. What does it print?

Exercise

K-th smallest in a BST

Write kth_smallest(root, k) that returns the k-th smallest value (1-indexed) in a BST. Use an iterative in-order traversal and stop as soon as you reach the k-th node.

In the BST built from [5, 3, 6, 2, 4, None, None, 1], kth_smallest(root, 3) is 3.