TraversalPre-, in-, post- and level-order traversal

01Why it exists

Reach for it when you see:Children before the node or the node first, listing values in ascending order, printing level by level, serialisation, BFS or DFS on a tree.

02The core idea

A traversal visits every node exactly once; only the order changes. The three depth-first traversals share an identical recursive skeleton — handle the left subtree, handle the right subtree, handle the node — and differ only in whether the line that handles the node comes first (preorder), in the middle (inorder), or last (postorder). The pre, in and post in the names refer to where the node sits relative to its two subtrees.

How to choose: use preorder when the answer is passed downwards (a path, a depth); postorder when it is assembled upwards (a height, a subtree sum); and inorder when you want sorted output from a BST. All three take O(n) time and O(h) space, where h is the height of the tree — the depth of the recursive call stack.

Level order uses no recursion at all, just a queue: pop a node, push its children onto the back. Because a queue is first in, first out, every node on one level sits ahead of every node on the next. To group the output level by level, record the current queue length at the start of each pass and handle exactly that many nodes. This is the tree version of BFS from graph theory, and its space is the number of nodes on the widest level.

When recursion goes deep enough to overflow the stack, simulate it with an explicit stack. The iterative inorder is the one that comes up most often: push nodes while walking as far left as you can, pop and visit when the left runs out, then turn to the right subtree. The key to understanding it is what the stack holds — nodes whose left side is not finished and which have not been visited themselves.

03The algorithm

1. 1Choose the order: preorder when the answer is carried downwards, postorder when it is assembled upwards, inorder when a BST has to come out sorted, and level order when you work one level at a time.
2. 2Recursive version: if node is None: return, then place the line that visits the node before, between, or after the two recursive calls.
3. 3Level-order version: push the root onto the queue; each pass pops a node, handles it, and pushes its children onto the back. To group by level, record the queue's length at the start of every pass.
4. 4When you need an iterative version, simulate it with a stack: preorder is the easiest (push the right child, then the left); inorder uses the go-left-as-far-as-possible pattern; postorder can be a node-right-left preorder that you reverse at the end.
5. 5Check the complexity: every node goes in and out once, so O(n); the extra space is the height of the tree (DFS) or the widest level (BFS).

04Interactive demo

Switch between the four traversals and step through the visiting order. The three depth-first ones show the call stack, and level order shows the queue. This tree's inorder happens to be 1 through 7, because it is a BST.

05Code

The three depth-first functions sit side by side, with only one line in a different place. Level order uses a queue and groups its output by level, and the last function is the iterative inorder.

from collections import deque


# Three depth-first traversals; the only difference is which line visits the node itself
def preorder(node, out):
    if node is None:
        return
    out.append(node.val)          # node
    preorder(node.left, out)      # left
    preorder(node.right, out)     # right

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)       # left
    out.append(node.val)          # node
    inorder(node.right, out)      # right

def postorder(node, out):
    if node is None:
        return
    postorder(node.left, out)     # left
    postorder(node.right, out)    # right
    out.append(node.val)          # node


# Level order: use a queue and handle one whole level at a time
def level_order(root):
    if root is None:
        return []
    out = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):   # this pass handles only the current level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        out.append(level)
    return out


# Iterative inorder: an explicit stack in place of recursion
def inorder_iter(root):
    out, stack, node = [], [], root
    while node or stack:
        while node:                   # go left as far as possible, pushing on the way
            stack.append(node)
            node = node.left
        node = stack.pop()            # no left child left, so visit the node itself
        out.append(node.val)
        node = node.right             # on to the right subtree

06Practice

• LeetCode 94Binary Tree Inorder Traversal (write it once recursively and once iteratively)Easy
• LeetCode 102Binary Tree Level Order TraversalMedium
• LeetCode 199Binary Tree Right Side View (level order, taking the last node of each level)Medium
• LeetCode 105Construct Binary Tree from Preorder and InorderMedium
• LeetCode 297Serialize and Deserialize Binary TreeHard
• LeetCode 236Lowest Common Ancestor (postorder thinking)Medium