Iterative Inorder Traversal: The Stack That Sorts Your BST

Three operations in a loop: push every node on the left spine onto a stack, pop and visit, then go right. That's the whole iterative inorder traversal. And when you run it on a binary search tree, you get every element in sorted order without doing any sorting. Not as a side effect. By construction.

This is Part 2 of a three-part series on iterative binary tree traversal. Part 1 covered preorder. Part 3 covers postorder.

Why Use Iterative Inorder Traversal?

Recursive inorder looks like this:

def inorder(node):
    if node:
        inorder(node.left)
        visit(node)
        inorder(node.right)

It's clean. It also blows the call stack on a skewed tree with 10,000 nodes. Python's default recursion limit is 1,000 frames. A perfectly left-skewed tree triggers a stack overflow before you visit a single node. Ten thousand nodes, zero visits, immediate crash.

Every time someone calls inorder on a 50k-node linked-list-shaped tree.

The iterative version replaces the call stack with an explicit one you control. Same algorithm, same result, no frame limit, and you get to reason about the space explicitly.

Push Left, Pop, Go Right

The invariant sounds fancier than it is. The stack always contains the ancestors of the current position whose left subtrees are still being explored. When you can't go further left, you owe a visit to the top of the stack.

from typing import Optional

class TreeNode:
    def __init__(self, val: int = 0, left: "Optional[TreeNode]" = None, right: "Optional[TreeNode]" = None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root: Optional[TreeNode]) -> list[int]:
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

The outer while current or stack condition is doing two jobs: current being set means there are nodes left to push; stack being non-empty means there are deferred visits to collect. The loop ends only when both are empty.

Notice what's not here: any special case for left-only nodes, right-only nodes, or leaves. The same three-line inner loop handles all of them.

After Phase 1: the left spine sits on the stack, current is null, and the algorithm is ready to start popping.

Running It by Hand

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

Step by step:

Phase 1: Push the left spine: 4, 2, 1. Stack: [4, 2, 1]. current = null.

Pop 1: Visit 1. current = null (no right child). Result: [1].

Pop 2: Visit 2. current = 3 (go right). Result: [1, 2].

Phase 2: Push the left spine from 3: just 3. Stack: [4, 3].

Pop 3: Visit 3. current = null. Result: [1, 2, 3].

Pop 4: Visit 4. current = 6. Result: [1, 2, 3, 4].

Phase 3: Push the left spine from 6: 6, 5. Stack: [6, 5].

Pop 5: Visit 5. current = null. Result: [1, 2, 3, 4, 5].

Pop 6: Visit 6. current = 7. Result: [1, 2, 3, 4, 5, 6].

Phase 4: Push 7. Stack: [7].

Pop 7: Visit 7. current = null. Stack empty. Done.

Output: [1, 2, 3, 4, 5, 6, 7].

The tree was sorting itself the whole time. You just needed to read it in the right order.

Each "phase" is a left-spine push. The algorithm never backtracks up the tree or looks for a parent pointer. The stack encodes all the ancestry information you need.

Why Inorder Sorts a BST

This is worth proving rather than just asserting.

The BST property says: for every node n, all values in n's left subtree are strictly less than n.val, and all values in n's right subtree are strictly greater than n.val.

Proof by structural induction:

Base case: a single node has no subtrees. Inorder yields [n.val]. Trivially sorted.

Inductive step: assume inorder produces a sorted sequence for any BST with k < n nodes. For a BST with n nodes rooted at r:

• By the inductive hypothesis, inorder(r.left) produces a sorted sequence where every element is less than r.val.
• By the inductive hypothesis, inorder(r.right) produces a sorted sequence where every element is greater than r.val.
• Inorder yields inorder(r.left) + [r.val] + inorder(r.right).
• A sorted sequence whose maximum is less than x, followed by x, followed by a sorted sequence whose minimum is greater than x, is sorted.

This is why inorder is the traversal for BST problems. Any problem asking for sorted order over a BST, or asking you to validate the BST property, or asking you to count elements relative to each other, routes through inorder.

The structure encodes the sort. Inorder just reads it out.

Space: Why O(h), Not O(n)

The stack never holds all n nodes simultaneously. At any moment it holds at most one node per depth level, because it stores a path from some ancestor down to the current leftmost frontier. A path in a tree has length at most h.

When you push the left spine of a subtree, you push at most h nodes. When you pop one and go right, you remove a node and may push a new spine, but you're trading stack slots, not accumulating them.

This means the space is O(log n) for a balanced BST and O(n) for a fully skewed one. For a balanced BST with a million nodes, the stack holds at most 20 nodes. That's worth knowing when you see this algorithm in a memory-constrained context.

The BST Iterator: Your Stack Is Already an Iterator

LeetCode 173 asks you to implement a BST iterator that yields elements in ascending order, with next() in O(h) time and O(h) space. Once you see the iterative inorder pattern, the solution is immediate.

The key insight: you don't need to traverse eagerly. The stack at any point IS the iterator state. Split the algorithm at the pop step and you have a resumable traversal.

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.stack: list[TreeNode] = []
        self._push_left(root)

    def _push_left(self, node: Optional[TreeNode]) -> None:
        while node:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

    def hasNext(self) -> bool:
        return bool(self.stack)

next() is O(h) worst case for a single call (when it triggers a long left-spine push on a right subtree). Amortized over n calls it's O(1), because each of the n nodes is pushed and popped exactly once across all invocations.

hasNext() is O(1). A non-empty stack means unvisited nodes exist.

The space stays O(h) throughout. The stack holds the pending ancestors, never the whole tree.

This pattern comes up in real systems too. A range scan over a B-tree index uses the same idea: maintain a pointer to the next leaf position, advance lazily on each next() call. The BST iterator is the simplified version.

Morris Traversal: Getting to O(1) Space

If O(h) space isn't good enough (say you're in a severely constrained environment), Morris traversal achieves O(1) by threading the tree.

The idea traces back to a question Donald Knuth posed in 1968: does a non-recursive inorder traversal exist that uses no stack and leaves the tree unmodified? Joseph M. Morris answered it in 1979 with a traversal that temporarily modifies the tree, then restores it.

For each node, Morris finds its inorder predecessor (the rightmost node in its left subtree) and threads that predecessor's null right pointer back to the current node. When you later arrive at the predecessor during traversal and see the thread pointing back, you know the left subtree is fully explored.

Morris borrows the null right pointers as temporary bookmarks, then puts them back. The tree is briefly inconsistent, which is fine as long as nothing else is reading it.

def morris_inorder(root: Optional[TreeNode]) -> list[int]:
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right is not current:
                predecessor = predecessor.right

            if predecessor.right is None:
                predecessor.right = current   # create thread
                current = current.left
            else:
                predecessor.right = None      # remove thread
                result.append(current.val)
                current = current.right
    return result

Time: O(n). The predecessor-finding inner loop looks expensive but it isn't. Each right pointer is traversed at most twice: once when threading (going right until null), once when checking if already threaded (going right until hitting current). Across all n nodes, total edge traversals are O(n).

Space: O(1). No stack. No recursion. Two pointers.

The catch: the tree is in a temporarily inconsistent state during traversal. If another thread reads the tree concurrently, it sees corrupt right pointers. Morris traversal is safe only in single-threaded contexts where you fully control when the tree is read.

The constant factor is also higher than the stack version. Morris traversal is for embedded systems, streaming contexts, and interviewers who want to see if you know it. In a standard interview setting, the stack-based version is the right answer 99% of the time.

Complexity at a Glance

h = tree height. O(log n) for a balanced BST, O(n) for a skewed one.

Each node is pushed and popped exactly once; that's the argument for O(n) time in every variant. No node is processed more than twice anywhere in this algorithm family.

One Structure, Every Language

The same algorithm in all fourteen languages. TreeNode definition and traversal included together.

from typing import Optional

class TreeNode:
    def __init__(self, val: int = 0, left: "Optional[TreeNode]" = None, right: "Optional[TreeNode]" = None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root: Optional[TreeNode]) -> list[int]:
    result: list[int] = []
    stack: list[TreeNode] = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

Where This Pattern Shows Up

BST-to-sorted-array: the traversal output directly is a sorted sequence. No additional processing needed.

BST validation: track the previously visited node during traversal and check that prev.val < current.val at each visit. One violation anywhere means the BST property is broken.

Kth smallest element: run inorder traversal and stop at the kth visit. O(h + k) time, O(h) space.

BST range queries: visit in sorted order, skip nodes outside the range, stop early once you've passed the upper bound.

BST to doubly linked list: during inorder traversal, stitch each visited node into a doubly linked list using its left and right pointers.

Successor/predecessor: to find a node's inorder successor, it's the leftmost node in its right subtree (if the right subtree exists), or the first ancestor for which the current node is in the left subtree. The iterator pattern makes this trivial: call next() one more time.

Merge two BSTs: run iterative inorder on both simultaneously (two stacks, two currents), and merge like merge sort.

How to Spot an Inorder Problem

Signal 1: BST + sorted order. Whenever a problem involves a BST and asks about relative ordering, sorted sequences, or ranks, inorder traversal is the tool. The sorted property comes for free.

Signal 2: "kth" queries on a BST. Problems asking for the kth smallest, kth largest, or median in a BST are inorder problems. You're just stopping or indexing into the sorted sequence.

Signal 3: validate BST. This is actually an inorder problem in disguise. The BST is valid if and only if inorder traversal produces a strictly increasing sequence.

Worked Example: Kth Smallest Element in a BST (LeetCode 230)

Problem: given the root of a BST and an integer k, return the kth smallest value.

Why inorder fits: the BST property guarantees that inorder traversal visits values in ascending order. The kth visit is exactly the kth smallest value.

Approach: run the iterative inorder algorithm. Keep a counter. When the counter hits k, return the current value immediately without traversing the rest of the tree.

def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right
    return -1

Time: O(h + k). Space: O(h). We stop early as soon as we find the answer.

Worked Example: Validate Binary Search Tree (LeetCode 98)

Problem: given the root of a binary tree, determine if it is a valid BST.

Why inorder fits: a tree is a valid BST if and only if its inorder traversal produces a strictly increasing sequence. So the problem reduces to: run inorder and check that each visited value is greater than the previous one.

def is_valid_bst(root: Optional[TreeNode]) -> bool:
    stack = []
    current = root
    previous_val: Optional[int] = None
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        if previous_val is not None and current.val <= previous_val:
            return False
        previous_val = current.val
        current = current.right
    return True

The previous_val check catches both equal values (which violate strict BST property) and out-of-order values. Time: O(n). Space: O(h).

The One-Paragraph Version

• Iterative inorder traversal pushes the left spine onto a stack, then pops-visits-goes-right, repeatedly.
• The outer loop condition current or stack handles all tree shapes without special cases.
• On a BST, inorder produces elements in sorted order. This follows by structural induction from the BST property.
• Space is O(h), not O(n): the stack holds a path, not a set of all pending nodes.
• The iterative pattern directly becomes a BST iterator. Split the algorithm at the pop step and you have next() and hasNext().
• Morris traversal achieves O(1) space by threading null right pointers as temporary back-links, then restoring them. O(n) time, safe only in single-threaded contexts.
• Key problems: kth smallest in BST, validate BST, BST iterator, BST to sorted array.

If you want to practice inorder traversal problems under interview pressure, SpaceComplexity runs voice-based mock interviews with rubric-based feedback. You'll know not just whether you got the answer right, but whether you explained the invariant clearly enough to convince an interviewer.

For related reading, the dynamic programming framework post covers how DP on trees often folds results up from leaves using a postorder pattern, which is the third traversal in this series.

Further Reading

• Binary Tree Inorder Traversal - GeeksforGeeks
• Threaded binary tree - Wikipedia
• Morris Traversal reconsidered - ScienceDirect
• BST Traversals - GeeksforGeeks
• LeetCode 94: Binary Tree Inorder Traversal
• LeetCode 173: Binary Search Tree Iterator