Tree Traversal: Inorder, Preorder, Postorder

A binary tree doesn’t have one obvious reading order the way a list does — before you can print, search, or process every node, you need a rule for the order in which you visit them. Tree traversal is that rule: a systematic way to visit every node in a tree exactly once. The three classic depth-first traversals — inorder, preorder, and postorder — all visit the same nodes, but they differ in exactly one thing: when the current node is visited relative to its left and right subtrees. That single difference is what makes each one suited to a different job, from printing a binary search tree in sorted order to evaluating an arithmetic expression tree.

Overview: How Tree Traversal Works

Every node in a binary tree has at most two children, referred to as its left and right subtrees. A traversal visits the current node and recursively traverses both subtrees — the only choice is when, relative to the two recursive calls, you actually “visit” (read, print, or process) the current node:

• Inorder — traverse the left subtree, visit the node, traverse the right subtree.
• Preorder — visit the node, traverse the left subtree, traverse the right subtree.
• Postorder — traverse the left subtree, traverse the right subtree, visit the node.

Consider this small tree of integers, built so it’s also a valid binary search tree (every node’s left subtree holds smaller values, its right subtree holds larger ones):

• 4 is the root, with left child 2 and right child 6
• 2‘s children are 1 (left) and 3 (right)
• 6‘s children are 5 (left) and 7 (right)

Because each traversal follows a fixed rule at every node, the entire tree ends up visited in one of three distinct sequences. Inorder gives 1, 2, 3, 4, 5, 6, 7 — the sorted order, precisely because this is a binary search tree and inorder always visits everything smaller before the node and everything larger after it. Preorder gives 4, 2, 1, 3, 6, 5, 7 — the root always comes first, which is exactly why preorder is used to serialize a tree (write down its structure so it can be rebuilt later): the very first value you read is always the root. Postorder gives 1, 3, 2, 5, 7, 6, 4 — every node’s children are fully processed before the node itself, which is exactly the property needed when a parent depends on results computed from its children, such as computing a subtree’s height or deleting a tree bottom-up so children are freed before their parent.

All three are usually implemented recursively, because the recursive structure of a tree maps directly onto the recursive structure of the traversal — traversing a tree is defined in terms of traversing its subtrees. Each recursive call handles a smaller tree, and the base case is always the same: an empty tree (a None node) requires no work at all.

Time and Space Complexity

All three traversals visit every node in the tree exactly once and do a constant amount of work per node (compare against None, append to a list, follow a pointer). That gives all three the same time complexity: O(n), where n is the number of nodes in the tree. There’s no way to do better than O(n), since visiting every node at least once is required by the very definition of “traversing” a tree.

Space complexity is more subtle, and it comes from the call stack, not the output list. Each recursive call adds a frame to Python’s call stack, and the maximum number of frames alive at any one moment equals the height of the tree, h — the length of the longest path from root to leaf. For a balanced tree, h is O(log n), since each level roughly doubles the number of nodes covered. For a completely unbalanced tree — say, every node has only a right child, so the tree degenerates into a linked list — h degrades all the way to O(n). So the auxiliary space used by a recursive traversal (excluding the space needed to store the result) is O(h), somewhere between O(log n) and O(n) depending on the tree’s shape.

The iterative, stack-based versions use exactly the same amount of memory — an explicit Python list standing in for the call stack — so their space complexity is identical. The difference is that the call stack has a hard limit (Python’s default recursion limit is around 1000 frames), so a very deep, unbalanced tree can make a recursive traversal raise a RecursionError, while the iterative version, using a plain list that grows on the heap, has no such ceiling.

Traversal	Visit order	Time	Auxiliary space
Inorder	left subtree, node, right subtree	O(n)	O(h)
Preorder	node, left subtree, right subtree	O(n)	O(h)
Postorder	left subtree, right subtree, node	O(n)	O(h)

n is the number of nodes and h is the height of the tree — O(log n) for a balanced tree, up to O(n) for a completely skewed one. This excludes the space needed for the result list itself, which is always O(n) if you materialize the full traversal.

Examples

Example 1: The three traversals, side by side

This example defines a small TreeNode class, builds the seven-node tree described above, and runs all three traversals on it so you can compare their output directly.

from typing import Optional


class TreeNode:
    def __init__(
        self,
        value: int,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def inorder(node: Optional[TreeNode], result: list[int]) -> None:
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.value)
    inorder(node.right, result)


def preorder(node: Optional[TreeNode], result: list[int]) -> None:
    if node is None:
        return
    result.append(node.value)
    preorder(node.left, result)
    preorder(node.right, result)


def postorder(node: Optional[TreeNode], result: list[int]) -> None:
    if node is None:
        return
    postorder(node.left, result)
    postorder(node.right, result)
    result.append(node.value)


# Tree layout: root 4, left subtree rooted at 2 (children 1 and 3),
# right subtree rooted at 6 (children 5 and 7).
root = TreeNode(4)
root.left = TreeNode(2, TreeNode(1), TreeNode(3))
root.right = TreeNode(6, TreeNode(5), TreeNode(7))

in_result: list[int] = []
pre_result: list[int] = []
post_result: list[int] = []

inorder(root, in_result)
preorder(root, pre_result)
postorder(root, post_result)

print("Inorder:", in_result)
print("Preorder:", pre_result)
print("Postorder:", post_result)

Output:

Inorder: [1, 2, 3, 4, 5, 6, 7]
Preorder: [4, 2, 1, 3, 6, 5, 7]
Postorder: [1, 3, 2, 5, 7, 6, 4]

Each traversal function follows the same shape: check the base case (node is None), then make two recursive calls and one “visit” (the result.append(node.value) line), just in a different order. Inorder’s visit sits between the two recursive calls, preorder’s visit comes before both, and postorder’s visit comes after both — that’s the entire difference between the three algorithms. Because this tree also happens to be a valid binary search tree, the inorder output comes out perfectly sorted; that’s not a coincidence, it’s the defining property of inorder traversal on a BST.

Example 2: Iterative inorder traversal with an explicit stack

Recursive traversals are easy to write but rely on Python’s call stack. This example rewrites inorder traversal iteratively, using an explicit stack (a plain Python list used with append/pop) to simulate what the call stack was doing. This pattern shows up constantly in interviews, since it demonstrates you understand what recursion is doing under the hood.

from typing import Optional


class TreeNode:
    def __init__(
        self,
        value: int,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def iterative_inorder(root: Optional[TreeNode]) -> list[int]:
    result: list[int] = []
    stack: list[TreeNode] = []
    current = root
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.value)
        current = current.right
    return result


# Same tree as before: root 4, left subtree rooted at 2 (children 1 and 3),
# right subtree rooted at 6 (children 5 and 7).
root = TreeNode(4)
root.left = TreeNode(2, TreeNode(1), TreeNode(3))
root.right = TreeNode(6, TreeNode(5), TreeNode(7))

print(iterative_inorder(root))

Output:

[1, 2, 3, 4, 5, 6, 7]

The idea is to walk as far left as possible, pushing every node onto the stack along the way (since none of them can be visited — added to the result — until their entire left subtree has been processed). Once there’s nowhere further left to go, pop the top of the stack, visit it, and then repeat the same “go as far left as possible” process starting from its right child. This produces exactly the same sequence as the recursive version, with the same O(h) auxiliary space bound, just without relying on Python’s own call stack.

Example 3: Evaluating an expression tree with postorder traversal

Postorder traversal isn’t just an academic exercise — it’s the natural way to evaluate an expression tree, where leaf nodes hold operands and internal nodes hold operators. You can’t apply an operator until you know the values of both of its children, which is exactly what postorder guarantees: children are fully processed before the parent. This example builds a tree for the expression (3 + 4) * (5 - 2), collects its postorder sequence (which is the classic postfix, or Reverse Polish, notation for the expression), and evaluates it.

from typing import Optional, Union


class ExprNode:
    def __init__(
        self,
        value: Union[int, str],
        left: Optional["ExprNode"] = None,
        right: Optional["ExprNode"] = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def collect_postorder(node: Optional[ExprNode], result: list[Union[int, str]]) -> None:
    if node is None:
        return
    collect_postorder(node.left, result)
    collect_postorder(node.right, result)
    result.append(node.value)


def evaluate(node: ExprNode) -> Union[int, float]:
    if node.left is None and node.right is None:
        return node.value
    left_value = evaluate(node.left)
    right_value = evaluate(node.right)
    if node.value == "+":
        return left_value + right_value
    if node.value == "-":
        return left_value - right_value
    if node.value == "*":
        return left_value * right_value
    if node.value == "/":
        return left_value / right_value
    raise ValueError(f"Unknown operator: {node.value}")


# Expression tree for (3 + 4) * (5 - 2)
root = ExprNode(
    "*",
    ExprNode("+", ExprNode(3), ExprNode(4)),
    ExprNode("-", ExprNode(5), ExprNode(2)),
)

postfix: list[Union[int, str]] = []
collect_postorder(root, postfix)
print("Postfix (postorder) form:", postfix)
print("Evaluated result:", evaluate(root))

Output:

Postfix (postorder) form: [3, 4, '+', 5, 2, '-', '*']
Evaluated result: 21

The postorder sequence 3, 4, '+', 5, 2, '-', '*' is exactly the postfix form of the expression: read left to right, each operator applies to the two values immediately before it. evaluate mirrors that logic recursively — it computes the left and right subtree values first (that recursion is itself doing a postorder walk), then combines them with the current node’s operator. 3 + 4 is 7, 5 - 2 is 3, and 7 * 3 is 21.

How It Works Step by Step

To see exactly how the recursion unfolds, trace preorder on the same seven-node tree (root 4, left subtree rooted at 2 with children 1 and 3, right subtree rooted at 6 with children 5 and 7). Preorder visits a node before either of its subtrees, so the trace below shows both the call order and the output as it accumulates.

1. Call preorder(4): 4 is not None, so visit it first — output so far: [4].
2. Call preorder(2) (the left child of 4): visit it — output: [4, 2].
3. Call preorder(1) (the left child of 2): visit it — output: [4, 2, 1].
4. 1 has no children, so preorder(None) is called for its left and right — both hit the base case and return immediately without touching the output.
5. Back inside the call for 2, its right child is visited next: preorder(3) visits 3 — output: [4, 2, 1, 3]. Its two children are None, so both calls hit the base case.
6. The call for 2 is now finished, so control returns to the call for 4, which moves on to its right child: preorder(6) visits 6 — output: [4, 2, 1, 3, 6].
7. Call preorder(5) (the left child of 6): visit it — output: [4, 2, 1, 3, 6, 5]. Its children are None, base case both times.
8. Call preorder(7) (the right child of 6): visit it — output: [4, 2, 1, 3, 6, 5, 7]. Its children are None, base case both times.
9. Every call has now returned, and the final preorder sequence is [4, 2, 1, 3, 6, 5, 7], matching the output shown in Example 1.

Notice that the recursion always goes as deep as possible down the left side before it ever touches a right subtree — that’s true for all three traversals, not just preorder. The only thing that changes between inorder, preorder, and postorder is where in that sequence of calls the “visit” step happens.

Common Mistakes

Mistake 1: Using a mutable default argument as the accumulator

A tempting way to write a traversal that “just returns a list” is to give the accumulator parameter a default value of []. This is one of Python’s most notorious gotchas: default argument values are evaluated once, when the function is defined, not once per call — so every call that doesn’t explicitly pass its own list ends up sharing and mutating the very same list.

from typing import Optional


class TreeNode:
    def __init__(
        self,
        value: int,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def preorder(node, result=[]):
    if node is None:
        return result
    result.append(node.value)
    preorder(node.left, result)
    preorder(node.right, result)
    return result


root_one = TreeNode(1, TreeNode(2), TreeNode(3))
root_two = TreeNode(9, TreeNode(8))

print(preorder(root_one))
print(preorder(root_two))

Output:

[1, 2, 3]
[1, 2, 3, 9, 8]

The second call was supposed to traverse a completely different, unrelated tree, but its result is contaminated with values left over from the first call — both calls were silently appending to the same shared list. The fix is to use None as the default and create a fresh list inside the function body when no list was passed in:

from typing import Optional


class TreeNode:
    def __init__(
        self,
        value: int,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


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


root_one = TreeNode(1, TreeNode(2), TreeNode(3))
root_two = TreeNode(9, TreeNode(8))

print(preorder(root_one))
print(preorder(root_two))

Output:

[1, 2, 3]
[9, 8]

Now each top-level call gets its own fresh list, and only the deliberate, explicit recursive calls (which pass result along on purpose) share it. This pattern — None as the default, with a real value constructed inside — is worth using anywhere a mutable object (list, dict, set) would otherwise sit in a default argument.

Mistake 2: Forgetting the base case

Every recursive traversal needs a base case that stops the recursion when it reaches an empty subtree (a None node). Forgetting the if node is None: return check doesn’t cause infinite recursion here — it causes an immediate crash, because the very next line tries to read an attribute off of None.

from typing import Optional


class TreeNode:
    def __init__(
        self,
        value: int,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def inorder(node, result):
    result.append(node.value)  # missing base case: no check for node is None
    inorder(node.left, result)
    inorder(node.right, result)


root = TreeNode(2, TreeNode(1), TreeNode(3))
collected = []
inorder(root, collected)
print(collected)

Output:

AttributeError: 'NoneType' object has no attribute 'value'

The function happily appends the root’s value, then recurses into its left child, then that node’s left child — and once it reaches a node whose child is genuinely absent (None), it tries to read node.value on None and blows up. The fix is the same base case every traversal needs:

from typing import Optional


class TreeNode:
    def __init__(
        self,
        value: int,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def inorder(node: Optional[TreeNode], result: list[int]) -> None:
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.value)
    inorder(node.right, result)


root = TreeNode(2, TreeNode(1), TreeNode(3))
collected: list[int] = []
inorder(root, collected)
print(collected)

Output:

[1, 2, 3]

Checking node is None before doing anything else is not optional boilerplate — it’s the base case that makes the recursion terminate correctly at every leaf’s missing children.

Best Practices

• Reach for inorder traversal whenever you need the contents of a binary search tree in sorted order — it’s the one traversal with a guaranteed ordering property, and it does it in O(n) without a separate sort.
• Reach for preorder when you need to serialize a tree (write it to a string, a file, or across a network) in a way that lets you rebuild it later, since the root is always the first value read — this is also why preorder is the natural way to copy or clone a tree, building new nodes top-down.
• Reach for postorder whenever a node’s result depends on its children’s results — computing a subtree’s height or size, evaluating an expression tree, or deleting/freeing a tree’s nodes (children must be freed before the parent that references them).
• For very deep or unbalanced trees, prefer the iterative, stack-based version over recursion — Python’s default recursion limit (around 1000 frames) can turn a recursive traversal on a large, skewed tree into a RecursionError, while an explicit stack has no such ceiling.
• Never use a mutable object (a list, dict, or set) as a default argument for an accumulator parameter — use None and construct the real value inside the function body instead.
• Remember that no single traversal alone can uniquely reconstruct an arbitrary binary tree, but a pair of traversals — most commonly preorder and inorder — can, which is why “reconstruct a binary tree from its traversals” is a common interview question.

Practice Exercises

1. Write a function is_same_tree(p, q) that takes the roots of two binary trees and returns True if they are structurally identical and have the same values at every position, False otherwise. Hint: you don’t need to build a full traversal list first — compare the two trees node by node, recursively, checking that both are None together, both are non-None with equal values, and both their left and right subtrees match.
2. Given the root of a binary search tree and an integer k, write a function kth_smallest(root, k) that returns the k-th smallest value in the tree. Hint: which traversal visits a BST’s nodes in sorted order? You don’t have to build the entire list before finding the answer — think about how you could stop early.
3. Write iterative_preorder(root): a preorder traversal that uses an explicit stack instead of recursion, mirroring the style of the iterative inorder traversal in Example 2. Hint: push the current node’s right child onto the stack before its left child, so that popping the stack visits the left child first.

Summary

• Inorder (left, node, right) visits a binary search tree’s nodes in sorted order.
• Preorder (node, left, right) visits the root first, making it the standard choice for serializing or cloning a tree.
• Postorder (left, right, node) visits children before their parent, making it the standard choice for evaluating expression trees or deleting a tree bottom-up.
• All three traversals run in O(n) time, since every node is visited exactly once.
• Auxiliary space is O(h), where h is the tree’s height — O(log n) for a balanced tree, up to O(n) for a completely skewed one — whether you use recursion (the call stack) or an explicit stack (the iterative versions).
• Avoid mutable default arguments (def f(x, acc=[])) in accumulator-style recursive functions, and always include a node is None base case — skipping either one is a common source of subtle or crashing bugs.
• No single traversal can uniquely reconstruct an arbitrary binary tree, but a pair of traversals (commonly preorder plus inorder) can.