BST Traversal Techniques

A BST traversal is a systematic walk over every node using the tree's own recursive left/right structure — the order in which you sequence the three actions (visit-left, visit-node, visit-right) determines whether you get sorted output, a rebuildable prefix, or a safe-to-delete postfix, so the traversal is really just a permutation of one recursive call.

Recognize the pattern

• The problem talks about a tree and asks for nodes "in order", "sorted", "level by level", or "process children before/after parent".
• You need to serialize a tree so it can be rebuilt identically (preorder), or process leaves before ancestors (postorder — safe deletion, directory-size aggregation, evaluating expression trees bottom-up).
• You need a BST's contents as a sorted stream without an extra sort step (inorder).
• Follow-up constraint appears: "O(1) extra space", "no recursion allowed", or "iterative only" — signals Morris traversal or explicit-stack simulation.

Brute force → optimal

Brute force: dump every node into an array via any order, then re-sort or re-filter to get what you need — e.g., collect all values and call Collections.sort() to get ascending order. Cost: O(n log n) time, ignoring the tree's structure entirely.

Optimal (recursive DFS): exploit the BST invariant directly — inorder visits left subtree (all smaller keys), then root, then right subtree (all larger keys), which is a sorted walk for free. O(n) time, O(h) space for the call stack.

Further optimal (Morris traversal): eliminate the O(h) stack by temporarily threading right pointers from each node's inorder predecessor back to itself, walking the thread, then removing it. O(n) time, O(1) space — at the cost of temporarily mutating the tree structure during the walk.

Complexity, derived

Recursive/iterative-stack DFS: the recurrence is T(n) = T(k) + T(n-k-1) + O(1) summed over all nodes, which telescopes to exactly n calls each doing O(1) work at the node itself → O(n) time. The stack depth at any moment equals the number of ancestors currently "open", which is bounded by the tree height h → O(h) space (O(log n) balanced, O(n) skewed, e.g. a tree built by inserting 1,2,3,...,n in order).

Morris traversal: each edge is traversed at most twice (once to create the thread, once to find and remove it while walking), so total pointer operations are bounded by 2n → still O(n) time, but no call stack or explicit stack is used → O(1) extra space (excluding the temporarily-modified tree itself, which is restored before returning).

Worked example

BST built by inserting 5, 3, 8, 1, 4, 7, 9 (shown in the diagram). Trace of the inorder recursive call stack:

Result: 1, 3, 4, 5, 7, 8, 9 — sorted, as guaranteed by the BST invariant. Preorder on the same tree gives 5, 3, 1, 4, 8, 7, 9 (root-first, useful to rebuild the exact same tree shape by re-inserting in that order); postorder gives 1, 4, 3, 7, 9, 8, 5 (children fully processed before parent, so free(node) after visiting children never dereferences freed memory).

Java (all three, plus Morris inorder)

class Node {
  int val; Node left, right;
  Node(int v) { val = v; }
}

class Traversals {
  static void inorder(Node n, List<Integer> out) {
    if (n == null) return;
    inorder(n.left, out);
    out.add(n.val);
    inorder(n.right, out);
  }

  static void preorder(Node n, List<Integer> out) {
    if (n == null) return;
    out.add(n.val);
    preorder(n.left, out);
    preorder(n.right, out);
  }

  static void postorder(Node n, List<Integer> out) {
    if (n == null) return;
    postorder(n.left, out);
    postorder(n.right, out);
    out.add(n.val);
  }

  // Morris inorder: O(1) extra space, temporarily threads the tree.
  static List<Integer> morrisInorder(Node root) {
    List<Integer> out = new ArrayList<>();
    Node cur = root;
    while (cur != null) {
      if (cur.left == null) {
        out.add(cur.val);
        cur = cur.right;
      } else {
        Node pred = cur.left;
        while (pred.right != null && pred.right != cur) pred = pred.right;
        if (pred.right == null) {
          pred.right = cur;      // create thread
          cur = cur.left;
        } else {
          pred.right = null;     // remove thread, restore tree
          out.add(cur.val);
          cur = cur.right;
        }
      }
    }
    return out;
  }
}

Pitfalls

• Confusing inorder-gives-sorted-order as a property of any binary tree — it only holds for a valid BST.
• Deep/skewed trees (e.g. built from already-sorted input) blow the recursion stack — O(n) space, not O(log n); use an explicit stack or Morris traversal for guaranteed depth safety.
• Forgetting to remove the Morris thread on the second visit — leaves the tree permanently corrupted (a right pointer pointing back up), breaking every subsequent operation.
• Using preorder/postorder when the task actually needs sorted output — off-by-one logic errors are often really an order-of-traversal error.

When to use / when not — trade-offs

Do not reach for Morris traversal by default: it is trickier to get right (the thread-removal bug above) and mutates the tree mid-traversal, which is unacceptable if another thread might read the tree concurrently.

Takeaways

• Inorder/preorder/postorder are the same recursive skeleton with the "visit" step moved — the BST invariant is what turns inorder into a sorted stream.
• Time is always O(n); space is the real design knob — O(h) call stack vs O(1) with Morris threading.
• Pick postorder whenever children must be fully handled before the parent (deletion, aggregation); preorder when the parent must be handled before children (cloning, serialization).

Recall: Why does an inorder traversal of a BST always produce ascending order, and what specifically breaks if you run it on an arbitrary (non-BST) binary tree?

Synthesized from standard BST traversal theory (Cormen et al., Introduction to Algorithms) and the Morris traversal technique (J.H. Morris, 1979, "Traversing Binary Trees Simply and Cheaply").