Tree Traversals

Visiting every node in an array is unambiguous — go left to right. Visiting every node in a tree is not: at each node you could visit it before, between, or after visiting its children, and you could go depth-first or breadth-first entirely. Each choice produces a different, useful order. Tree traversal is the name for these four standard patterns, and knowing which one to reach for is what turns "walk the tree" into "print it sorted" or "evaluate this expression correctly."

The idea: when do you visit the node itself, relative to its children

For a binary tree, three depth-first orders differ only in when the current node is processed relative to recursing into its left and right children:

• Preorder (node, left, right): visit the node first, then descend. Useful for copying a tree or serializing it in a way that reconstructs the same shape.
• Inorder (left, node, right): visit the node between its children. For a binary search tree specifically, this visits nodes in sorted order — the one traversal with a built-in ordering guarantee.
• Postorder (left, right, node): visit the node last, after both children. Useful whenever a node depends on its children being fully processed first — computing a subtree's size, deleting a tree bottom-up, or evaluating an expression tree (evaluate both operands before applying the operator).

A fourth pattern, level-order (breadth-first), visits all nodes at depth 0, then depth 1, then depth 2, using a queue instead of recursion — see Graph Traversal — BFS and DFS for the same idea applied to general graphs.

Worked example: BST [5, 3, 8, 1, 4, 7, 9]

Tree shape: root 5, left child 3 (children 1, 4), right child 8 (children 7, 9).

• Preorder (node, left, right): 5, 3, 1, 4, 8, 7, 9
• Inorder (left, node, right): 1, 3, 4, 5, 7, 8, 9 — exactly sorted, because at every node everything smaller (left subtree) is visited first and everything bigger (right subtree) last.
• Postorder (left, right, node): 1, 4, 3, 7, 9, 8, 5 — the root comes out last, useful if you're about to delete the tree and need every child freed before its parent.
• Level-order: 5, 3, 8, 1, 4, 7, 9 — by depth, not by subtree.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def inorder(node, out):              # O(n) time, O(h) recursion depth
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)

Where it shows up

Interviewers ask for all three depth-first orders both recursively and iteratively (using an explicit stack instead of the call stack — see Stacks and Queues), plus level-order with a queue, and follow-ups like "serialize and deserialize a binary tree" that lean directly on preorder. In quant systems, postorder shows up when evaluating a parsed expression tree (an options payoff formula, a factor-combination DAG) bottom-up so every subexpression is resolved before the node that consumes it runs, and inorder traversal of a tree-backed order book gives prices in sorted order without a separate sort step.