Tree Traversal Explained (Inorder, Preorder, Postorder)

Traversal means visiting every node in a tree exactly once, in some defined order. Unlike an array or list, a tree doesn't have one obvious "left to right" order to walk through — depending on when you visit a node relative to its children, you get a completely different sequence of values. Knowing these traversal orders matters because many tree algorithms are really just "do a traversal, and do something specific when you visit each node."

The three classic depth-first orders — inorder, preorder, and postorder — all use the same recursive shape and only differ in when they process the current node relative to its children.

Example Tree

All three examples below walk this same small tree:

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

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

root = Node(4,
    Node(2, Node(1), Node(3)),
    Node(6, Node(5), Node(7)))

Inorder: Left, Node, Right

Visit the left subtree, then the current node, then the right subtree. On a binary search tree, this produces values in fully sorted order — which is the main reason this traversal matters so much in practice.

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

print(inorder(root))

Output:

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

Preorder: Node, Left, Right

Visit the current node before either subtree. This is useful when you need to process a node before its children — for example, copying a tree, or serializing it in a way that lets you reconstruct it by reading top to bottom.

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

print(preorder(root))

Output:

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

Postorder: Left, Right, Node

Visit both subtrees before the current node. This order matters whenever children must be fully handled before the parent — deleting a tree node by node (you must free the children first), or evaluating an expression tree (you need both operands before you can apply the operator at the parent).

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

print(postorder(root))

Output:

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

Bonus: Level-Order Traversal (BFS)

All three orders above are depth-first — they dive down one branch before backtracking. Level-order traversal instead visits the tree level by level, top to bottom, left to right, using a queue instead of recursion. It's really the same idea as BFS on a graph, just applied to a tree.

from collections import deque

def level_order(root):
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

print(level_order(root))

Output:

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

Each of these runs in O(n) time since every node is visited exactly once, and O(h) extra space for the recursive call stack (or O(w) for the widest level, in the queue-based version) — details worth keeping in mind alongside the general Big O analysis of any tree algorithm you write.