Binary Tree Traversal: The Node, the Stack, and the Four Traversals

You get a binary tree traversal problem in an interview. You vaguely remember preorder versus inorder. You start writing. Somewhere around the second recursive call, you've confused yourself, the interviewer is watching, and your code no longer matches what you're explaining.

Here's the reference for before that moment. Every traversal, how they work under the hood, why the space complexity is O(h) and not O(n) most of the time, and the signal that tells you which one to grab.

Sometimes it's a hashmap. Sometimes it's preorder. The planning face is the same either way.

What a Binary Tree Is

A binary tree is a collection of nodes where each node holds a value and at most two children: left and right. That's the entire definition. No ordering constraint (that's BST territory), no balance requirement (that's AVL or red-black territory). Just nodes with up to two kids.

The mental model that sticks: a binary tree is a recursive structure. Each subtree is itself a binary tree. That recursion in the definition is exactly why recursive code fits so naturally onto trees. The shape of the algorithm mirrors the shape of the data.

You reach for a binary tree when your data has a natural branching structure: ordered containers, expression trees, file system hierarchies, priority queues.

How a Binary Tree Lives in Memory

The Node Structure

Each node is a small heap-allocated object with three fields. Here's what it looks like in C on a 64-bit system:

typedef struct TreeNode {
    int val;             // 4 bytes
    // 4 bytes padding (compiler aligns pointers to 8-byte boundaries)
    struct TreeNode* left;   // 8 bytes
    struct TreeNode* right;  // 8 bytes
} TreeNode;              // 24 bytes total per node

┌──────────┬──────────┬──────────┬──────────┐
│  val (4) │ pad (4)  │ left (8) │ right (8)│
└──────────┴──────────┴──────────┴──────────┘
             24 bytes per node, 64-bit system

24 bytes per node, scattered individually across the heap. Those two pointer fields are the entire shape of the tree.

The root's address lives in a variable on the stack. Every node lives on the heap, allocated individually. The tree's shape is entirely in those pointer fields: set left or right to null, and that branch doesn't exist.

This matters for performance. Nodes are scattered across the heap, not contiguous. Walking from parent to child involves pointer dereferences that regularly miss the CPU cache. Arrays (like in a binary heap stored as a flat array) have 2x to 5x better cache locality for traversal-heavy workloads. If you care about performance constants, not just Big O, this is where the tree pays a tax.

In Python, each node is a full Python object. The PyObject overhead (reference count, type pointer, garbage collection header) adds roughly 56 bytes before you even store the integer value. A Java TreeNode carries its own JVM object header. The abstract structure is the same; the constant factor in memory varies by 2x to 10x depending on language.

The Three Shapes a Tree Can Take

Height h of a tree on n nodes ranges from O(log n) for a perfect tree to O(n) for a degenerate one. This range is not academic. Every complexity claim about trees has h in it somewhere.

Perfect binary tree (h ≈ log₂ n):        Skewed tree (h = n-1):
           1                                   1
         /   \                                  \
        2     3                                  2
       / \   / \                                  \
      4   5 6   7                                  3
                                                    \
                                                     4

Same definition, wildly different performance. Both are valid binary trees. Only one will blow your call stack.

A skewed tree is a linked list wearing a tree costume. Recursion on a skewed tree of a million nodes blows the call stack, because you need a million stack frames. The O(h) guarantee only means O(log n) if someone kept the tree balanced.

Core Operations

All four traversals touch every node exactly once: O(n) time with no exceptions.

The O(h) space for DFS is not hand-wavy. Here is the exact accounting. At any moment during a recursive inorder traversal, the call stack holds exactly the ancestors of the currently-active node, from root down to the deepest live frame. The maximum number of simultaneously-live frames is h+1. Each frame holds a constant amount of data (one pointer, one return address, a few register saves). So the call stack occupies O(h) space.

Note what this does not say: the frames for the left subtree and the right subtree are never both alive at the same time. You finish the left subtree entirely, pop all those frames, then start the right. Peak stack depth equals tree height, not 2 * tree height.

For BFS, the queue at its fullest holds all nodes at the widest level. In a perfect binary tree, the bottom level has ceil(n/2) nodes. That is O(n). For a skewed tree, every level has exactly one node, so the queue never exceeds size 1. The worst-case BFS space is O(n). Neither DFS nor BFS dominates the other in space across all inputs.

The Four Binary Tree Traversals

Same tree. Four completely different visit sequences. The badge is when that node gets visited, not the node's value.

Preorder: Root, Left, Right

Process the node, then recurse left, then recurse right. You see every node before any of its descendants.

Tree:          Preorder visits:
     1             1, 2, 4, 5, 3, 6, 7
   /   \
  2     3
 / \   / \
4   5 6   7

The recursive implementation is essentially trivial. The key insight for the iterative version: push right before left, so left pops first.

# Iterative preorder
def preorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

When you need it: copying a tree, serializing it, generating prefix (Polish notation) expressions, or any problem where a parent's context must be established before visiting children.

Inorder: Left, Root, Right

Recurse left, then process the node, then recurse right.

Inorder visits: 4, 2, 5, 1, 6, 3, 7

For any BST, inorder traversal produces values in sorted order. That one property drives an entire class of interview problems: finding the kth smallest element, converting a BST to a sorted array, validating a BST, recovering a BST with two swapped nodes. All lean on inorder.

The iterative version reveals the underlying mechanics clearly. You keep descending left, pushing nodes as you go, until you hit null. Then you pop, process, and move right. That right move may itself trigger another left-descent chain.

Iterative inorder state on the tree above:

Step 1: current=1, stack=[]  → push 1, go left
Step 2: current=2, stack=[1] → push 2, go left
Step 3: current=4, stack=[1,2] → push 4, go left
Step 4: current=null, stack=[1,2,4] → pop 4, visit 4, go right (null)
Step 5: current=null, stack=[1,2] → pop 2, visit 2, go right (5)
Step 6: current=5, stack=[1] → push 5, go left (null)
Step 7: current=null, stack=[1,5] → pop 5, visit 5, go right (null)
Step 8: current=null, stack=[1] → pop 1, visit 1, go right (3)
... and so on

When you need it: sorted output from a BST, finding kth smallest, flattening a BST to a sorted array, Morris traversal (see below).

Postorder: Left, Right, Root

Recurse left, recurse right, then process the node. You see every node after all of its descendants.

Postorder visits: 4, 5, 2, 6, 7, 3, 1

This is the "gather results from children, then compute at parent" pattern. Any problem where a node's answer depends on values from its subtrees uses postorder logic. Tree height, diameter, subtree sum, LCA (lowest common ancestor): all postorder.

The iterative postorder is the trickiest of the three. The clean single-stack approach tracks the previously-visited node to know whether the right subtree has already been processed.

# Iterative postorder (single stack)
def postorder_iterative(root):
    result = []
    stack = []
    current = root
    prev = None
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        top = stack[-1]
        if top.right and top.right is not prev:
            current = top.right
        else:
            result.append(top.val)
            prev = stack.pop()
    return result

When you need it: tree deletion, evaluating expression trees, computing subtree aggregates (size, sum, height), finding tree diameter, checking tree symmetry.

Level-Order: Breadth First

Visit nodes level by level, left to right within each level. A queue makes this clean.

Level-order visits: 1 | 2, 3 | 4, 5, 6, 7
                    ^   ^^  ^    ^  ^  ^  ^
                   L0   L1       L2 (level 2)

Queue evolution:
Start:  [1]
After 1: [2, 3]
After 2: [3, 4, 5]
After 3: [4, 5, 6, 7]
After 4: [5, 6, 7]
...

The queue at its widest holds ⌈n/2⌉ nodes (the whole bottom level of a perfect tree). That's O(n) space, not O(1).

The standard interview pattern captures each level as its own list by freezing the queue size at the start of each iteration. Everything currently in the queue belongs to the current level. Anything you enqueue during the iteration belongs to the next one.

When you need it: minimum depth (first leaf found is guaranteed shallowest), right side view, zigzag traversal, connecting nodes at the same level, anything that says "level by level."

Binary Tree Traversal Space Complexity: Stack vs Heap

Two kinds of memory are in play during any tree traversal. They're unrelated and often confused.

The heap: All the nodes. Allocated when the tree was built. Size O(n). Your traversal function only reads it, it does not grow or shrink it.

The call stack: The frames your recursion creates. Each frame is born when you call traverse(node) and dies when that call returns.

def inorder(node):
    # ← this frame is on the call stack from here...
    if node is None:
        return              # ← ...to here (immediate return)
    inorder(node.left)      # new frame pushed; this frame pauses
    visit(node)
    inorder(node.right)     # new frame pushed; this frame pauses
    # ← ...to here (return after right subtree)

The deepest the stack ever gets is when you're at the leftmost leaf of the current left-descending chain. At that moment, the stack holds exactly the ancestors of that leaf. That depth is h.

The critical insight: the frames for the left subtree and right subtree are never alive at the same time. When you finish the left subtree and start the right, all those left subtree frames have already returned and been popped. The peak stack depth is h, not 2h, not n.

For a balanced tree with n = 1,000,000:
  h = log₂(1,000,000) ≈ 20
  Peak frames alive: ~21

For a skewed tree with n = 1,000,000:
  h = 999,999
  Peak frames alive: 1,000,000
  Python default recursion limit: 1,000 → RecursionError

Three frames alive at peak, not seven, not n. Left and right subtrees take turns on the stack and never overlap.

This is why the iterative implementations exist. They move the stack from the language runtime onto the heap, where you control the size. The algorithm is identical. The substrate is different. Python is just the most vocal about it.

Morris Traversal: O(1) Space

If you need inorder traversal with genuinely no extra space (no explicit stack, no recursion), Morris traversal does it in O(n) time and O(1) space. The trick is temporary pointer threading.

For each node with a left subtree, find the rightmost node in that left subtree (the inorder predecessor) and set its right pointer to the current node. This creates a "way back" after the left subtree finishes. After visiting the current node, the thread is followed, then removed, restoring the original structure.

The algorithm is non-trivial to implement under pressure. Know it exists, understand the threading idea, and be ready to explain why it works. You will understand it once, feel briefly proud, and forget the exact steps by next week. That's fine. Knowing it exists and why the threading works is the interview win.

Implementations

Same four traversals, many languages. The logic is identical across all of them; only the syntax changes.

from collections import deque
from typing import Optional

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

def preorder(root: Optional[TreeNode]) -> list[int]:
    result: list[int] = []
    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        result.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return result

def inorder(root: Optional[TreeNode]) -> list[int]:
    result: list[int] = []
    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result

def postorder(root: Optional[TreeNode]) -> list[int]:
    result: list[int] = []
    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)
    dfs(root)
    return result

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    if root is None:
        return []
    result: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])
    while queue:
        level: list[int] = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

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

What Problems Binary Trees Solve

The canonical use cases:

• Ordered storage with fast operations. BSTs give O(log n) search, insert, and delete on balanced trees. Every sorted container in every standard library is a balanced BST variant under the hood.
• Priority queues. Binary heaps are complete binary trees, usually stored as flat arrays. The heap property (parent always smaller than children, or vice versa) is maintained by sifting.
• Expression evaluation. Expression trees put operators at internal nodes and operands at leaves. Evaluating the tree is postorder traversal.
• Hierarchical data. File systems, HTML/XML DOMs, organizational charts: any structure where each entity has a parent and up to two categorically-distinct children.
• Divide-and-conquer algorithms. Many D&C algorithms naturally build implicit binary trees. Merge sort's recursion tree is a perfect binary tree. The stack space analysis is the same: O(log n) for a balanced split, O(n) if you're unlucky.
• Decision trees. Machine learning decision trees, game trees for minimax search, Huffman coding trees: all use the binary tree structure with some variant of DFS traversal.

Recognizing the Pattern

Two traversal shapes cover most tree interview problems. Before writing a single line, ask yourself one question: does the current node need information from its children, or does it provide information to its children?

Shape 1: Pass information down (preorder, top-down)

The function takes extra parameters from its caller. Computation happens when you visit the node, before the recursive calls.

Problem: Does any root-to-leaf path sum to a target?

Given a binary tree and target T, return true if there is a
root-to-leaf path where all node values sum to T.

Why this fits: each node on the path contributes its value. You need to know the "remaining budget" at each node, which comes from the ancestor chain. Parent provides context to child. Preorder shape.

def has_path_sum(node, remaining):
    if node is None:
        return False
    remaining -= node.val
    if node.left is None and node.right is None:
        return remaining == 0
    return has_path_sum(node.left, remaining) or has_path_sum(node.right, remaining)

Information flows root to leaves. Preorder.

Shape 2: Gather information up (postorder, bottom-up)

The function returns something useful to its caller. Computation happens after both recursive calls return.

Problem: Maximum depth of a binary tree.

Given a binary tree, return its maximum depth (number of nodes
along the longest root-to-leaf path).

Why this fits: you cannot know a node's depth contribution until you know how deep its subtrees go. Children must report their depths first. Child provides data to parent. Postorder shape.

def max_depth(node):
    if node is None:
        return 0
    left_depth = max_depth(node.left)
    right_depth = max_depth(node.right)
    return max(left_depth, right_depth) + 1

Information flows leaves to root. Postorder.

Most "hard" tree problems are postorder problems in disguise. Diameter of binary tree, binary tree cameras, maximum path sum: they all require each node to aggregate information from its subtrees before the parent can use that information. If you're stuck on a tree problem and preorder isn't clicking, flip it to postorder and ask what each node should return to its parent.

Other signals that say "tree problem"

• "For each node, its left subtree satisfies X" (BST property)
• "Find the lowest common ancestor of two nodes"
• "Serialize and deserialize a binary tree"
• "Check if two trees are identical / mirror images"
• "Count nodes / paths with property X"
• The input literally is a tree node pointer

One thing to watch: problems with "parent pointers" or "go to any adjacent node" are graph problems, not tree problems. If a node can be reached from multiple parents, you're not in tree territory anymore.

What to Remember

• A binary tree node has three fields: value, left pointer, right pointer. On a 64-bit system that's 24 bytes per node, with 4 bytes padding for alignment.
• Four traversals: preorder (root first), inorder (root middle), postorder (root last), level-order (BFS, queue-based).
• All four traversals visit every node once: O(n) time.
• DFS traversals use O(h) space. BFS uses O(w) space where w is the max width. Both degrade to O(n) in the worst case.
• O(h) space comes from the call stack depth, not from the heap nodes. Left and right subtrees never have simultaneous live frames.
• O(h) means O(log n) on a balanced tree and O(n) on a skewed one.
• Recursive and iterative DFS implement the same algorithm. Iterative just uses an explicit stack instead of the call stack.
• Inorder on a BST produces sorted output.
• Preorder shape: parent passes context down to children. Postorder shape: children return data up to parent.
• Python's default recursion limit is 1,000. For deep trees, write iterative versions.
• Morris traversal achieves O(1) space inorder traversal by threading temporary pointers.

If tree problems still make you reach for scratch paper first, you probably need reps under pressure, not more reading. SpaceComplexity runs voice-based mock interviews on exactly these problems and gives you rubric-based feedback on your communication alongside your code. A few sessions makes the traversal shapes feel automatic.

Tree recursion is also the foundation for dynamic programming on trees, and if you freeze mid-traversal trying to remember which order is which, the advice in Stuck in a Coding Interview? Don't Go Silent. applies directly.

Further Reading

• Binary tree (Wikipedia)
• Tree traversal techniques (GeeksforGeeks)
• Morris inorder traversal (GeeksforGeeks)
• Tree algorithms cheatsheet (Tech Interview Handbook)
• Binary tree (NIST Dictionary of Algorithms and Data Structures)