Binary tree traversal: inorder, preorder, postorder and level order

Tree traversal visits every node of a tree exactly once in a fixed order. Preorder visits the root, then the left subtree, then the right. Inorder visits left, root, right. Postorder visits left, right, root. Level order visits nodes depth by depth from the root, using a queue. Each traversal takes O(n) time for n nodes.

What is a tree structure, and what is a binary tree?

A tree is a data structure accessed from a root node. NIST's Dictionary of Algorithms and Data Structures describes each node as either a leaf or an internal node. An internal node has one or more child nodes and is the parent of those children, and children of the same node are siblings. A binary tree is a tree with at most two children per node, a left child and a right child.

The examples below use this tree, which is also a binary search tree: every key in a node's left subtree is smaller than the node's key, and every key in the right subtree is larger.

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \    /
       4   7  13

The root is 8. The leaves are 1, 4, 7 and 13. The tree has nine nodes and four levels.

What are the four traversal orders?

Three of the orders are depth-first and one is breadth-first. NIST defines each: preorder processes the root and then the subtrees, inorder processes the left subtree, the root and then the right subtree, postorder processes the subtrees and then the root, and level-order processes nodes by depth, equivalent to a breadth-first search from the root. Preorder is also called prefix traversal, inorder symmetric traversal and postorder postfix traversal.

To follow inorder by hand, start at 8 and keep going left to 3 and then 1. Node 1 has no left child, so it is visited first. Back at 3, visit 3, then go right to 6, where the left child 4 is visited, then 6, then 7. Return to 8 and visit it. Then go right to 10, which has no left child, visit 10, and go right to 14, visiting its left child 13 before 14 itself.

How do you code the traversals recursively and without recursion?

A recursive traversal is a direct transcription of the rule. Open Data Structures notes that recursion makes it very easy to compute facts about binary trees. The code below builds the example tree and prints all four orders. Level order uses a queue, and Python's deque is the right container because, according to the Python documentation, it supports appends and pops from either end in O(1), while list.pop(0) costs O(n).

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

root = Node(8,
            Node(3, Node(1), Node(6, Node(4), Node(7))),
            Node(10, None, Node(14, Node(13))))

def preorder(n, out):
    if n:
        out.append(n.val); preorder(n.left, out); preorder(n.right, out)

def inorder(n, out):
    if n:
        inorder(n.left, out); out.append(n.val); inorder(n.right, out)

def postorder(n, out):
    if n:
        postorder(n.left, out); postorder(n.right, out); out.append(n.val)

for name, fn in (("preorder", preorder), ("inorder", inorder), ("postorder", postorder)):
    out = []
    fn(root, out)
    print(f"{name:<10}", out)

preorder   [8, 3, 1, 6, 4, 7, 10, 14, 13]
inorder    [1, 3, 4, 6, 7, 8, 10, 13, 14]
postorder  [1, 4, 7, 6, 3, 13, 14, 10, 8]

Level order needs a queue, so it comes next, reusing the same tree.

from collections import deque

def level_order(n):
    out, q = [], deque([n])
    while q:
        node = q.popleft()
        out.append(node.val)
        for child in (node.left, node.right):
            if child:
                q.append(child)
    return out

print(f"{'level':<10}", level_order(root))

level      [8, 3, 10, 1, 6, 14, 4, 7, 13]

Level order starts with the queue holding only 8. Removing 8 adds its children 3 and 10. Removing 3 adds 1 and 6, removing 10 adds 14, and so on, so the nodes come out level by level, left to right within each level.

The depth-first orders can also run without recursion, using an explicit stack. The functions below reuse Node and root from the first sample. Inorder pushes the left spine, pops a node, visits it and moves right. Preorder pops a node, visits it and pushes its right child before its left so the left comes off first. Postorder is preorder with the roles of left and right swapped and the final list reversed.

def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                 # walk left as far as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)        # visit
        node = node.right
    return out

print(inorder_iter(root))

[1, 3, 4, 6, 7, 8, 10, 13, 14]

Preorder and postorder follow the same stack idea.

def preorder_iter(root):
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)   # push right first so left pops first
        if node.left:  stack.append(node.left)
    return out

def postorder_iter(root):
    out, stack = [], [root]
    while stack:                    # root, right, left ... then reverse
        node = stack.pop()
        out.append(node.val)
        if node.left:  stack.append(node.left)
        if node.right: stack.append(node.right)
    return out[::-1]

print(preorder_iter(root))
print(postorder_iter(root))

[8, 3, 1, 6, 4, 7, 10, 14, 13]
[1, 4, 7, 6, 3, 13, 14, 10, 8]

Why does inorder traversal of a binary search tree give sorted order?

Inorder traversal of a binary search tree gives sorted order because of the definition of the tree. NIST defines a binary search tree as one where every node's left subtree has keys less than the node's key and every right subtree has keys greater. Princeton's Algorithms text makes the argument for a printing routine: print all keys in the left subtree, which are less than the root by definition, then the root key, then all keys in the right subtree, which are greater.

Apply that argument at every node and the output is ascending. The inorder row in the table above, 1 3 4 6 7 8 10 13 14, is the sorted list of the tree's keys. The property holds only for a true binary search tree. On an arbitrary binary tree, inorder simply yields left-root-right order, with no sortedness.

Where are the traversal orders used?

Expression trees show the three depth-first orders most clearly. Cornell's CS2110 lecture notes use the expression tree for (2 × 1) - (1 + 0), where preorder gives the prefix form, postorder gives the postfix form and inorder gives the original expression except for the parentheses. Prefix is also called Polish notation and postfix reverse Polish notation. Postfix needs no brackets, and a stack evaluates it left to right.

# (3 + 4) * 5 as an expression tree; reuses Node from the first sample
expr = Node("*", Node("+", Node(3), Node(4)), Node(5))

def walk(n, order, out):
    if n is None: return
    if order == "pre": out.append(n.val)
    walk(n.left, order, out)
    if order == "in": out.append(n.val)
    walk(n.right, order, out)
    if order == "post": out.append(n.val)

for order in ("pre", "in", "post"):
    out = []; walk(expr, order, out)
    print(order, " ".join(map(str, out)))

pre * + 3 4 5
in 3 + 4 * 5
post 3 4 + 5 *

A stack evaluates the postfix list from left to right. Numbers are pushed, and each operator pops two values and pushes the result.

def eval_postfix(tokens):
    stack = []
    for t in tokens:
        if isinstance(t, int):
            stack.append(t)
        else:
            b, a = stack.pop(), stack.pop()
            stack.append(a + b if t == "+" else a * b)
    return stack[0]

post = []; walk(expr, "post", post)
print(eval_postfix(post))

35

The inorder line shows why infix needs brackets: 3 + 4 × 5 would normally mean 3 + 20, but the tree means (3 + 4) × 5. Preorder with a marker for each empty child also serialises a tree to text and rebuilds it. The sample writes the example tree as 8,3,1,#,#,6,4,#,#,7,#,#,10,#,14,13,#,#,# and reads it back into an identical tree.

def serialize(n, out):
    if n is None:
        out.append("#")
    else:
        out.append(str(n.val)); serialize(n.left, out); serialize(n.right, out)

def deserialize(tokens):
    t = next(tokens)
    if t == "#": return None
    return Node(int(t), deserialize(tokens), deserialize(tokens))

out = []; serialize(root, out)
text = ",".join(out)
print(text)
copy = deserialize(iter(text.split(",")))
again = []; serialize(copy, again)
print(again == out)

8,3,1,#,#,6,4,#,#,7,#,#,10,#,14,13,#,#,#
True

Level order suits any task that handles a tree one depth at a time. Related structures appear in Tree Data Structure: Types, Operations, Applications, and the heap in heap data structure and priority queue explained is a tree stored in an array.

What is the time and space complexity of tree traversal?

Every traversal visits each node once, so time is O(n). Space differs. A depth-first traversal holds a stack as deep as the tree is tall, and a level-order traversal holds a queue as wide as the widest level. On the example tree each traversal visits all nine nodes, the tree is four levels tall, and the queue never holds more than three nodes.

For a balanced tree the height is about log n, so the stack stays small. For a tree that degenerates into a chain, the height is n.

What can go wrong with recursive traversal?

Open Data Structures points out that the maximum depth of recursion equals the tree's height, and that a very tall tree could use more stack space than is available and crash. Python makes the limit explicit: the documentation says sys.getrecursionlimit() returns the maximum depth of the interpreter stack, which prevents infinite recursion from overflowing the C stack.

The next sample builds a left-leaning chain of 5,000 nodes. The recursive inorder from the first sample fails with RecursionError, while the iterative version handles the same tree. It reuses inorder and inorder_iter from the earlier samples.

import sys
chain = None                       # a left-leaning chain of 5000 nodes
for v in range(5000):
    chain = Node(v, chain)

print("recursion limit:", sys.getrecursionlimit())
try:
    inorder(chain, [])
except RecursionError:
    print("recursive traversal: RecursionError")
print("iterative traversal visited", len(inorder_iter(chain)), "nodes")

recursion limit: 1000
recursive traversal: RecursionError
iterative traversal visited 5000 nodes

Other frequent mistakes are forgetting the null check for a missing child, visiting a node before its subtrees in postorder, and using list.pop(0) instead of a deque for the level-order queue. Choosing the order matters too: use inorder for sorted output, preorder to copy or serialise, postorder when parents depend on children, and level order for depth-wise work.

Where does tree traversal fit for working engineers?

Traversals are the standard way to process tree-shaped data, from expression trees to search trees. The Forward Deployed Engineer (FDE) Cohort is a Leap by Masai programme for engineers with hands-on technical experience, run as an in-person start in Goa, an online build phase and an in-person hackathon in Bangalore for qualifying participants, covering production Python, APIs, cloud deployment, LLMs, retrieval, agents, security and client engagement.

Its content includes production-ready Python and data pipelines, APIs and access. Details are on the Forward Deployed Engineer cohort page.

Frequently asked questions

What is the difference between preorder and postorder traversal?

Preorder processes a node before its subtrees: root, left, right. Postorder processes a node after its subtrees: left, right, root. On the example tree preorder gives 8 3 1 6 4 7 10 14 13 and postorder gives 1 4 7 6 3 13 14 10 8. Preorder suits copying a tree, postorder suits work that needs children first.

Why does inorder traversal of a BST give sorted order?

A binary search tree keeps smaller keys in the left subtree and larger keys in the right subtree. Inorder visits the left subtree, then the node, then the right subtree, so at every node smaller keys come out first, then the node, then larger keys. Applied at every level, the output is ascending.

What is level order traversal?

Level order traversal visits a tree depth by depth, starting with the root and then its children, moving left to right on each level. It is equivalent to a breadth-first search from the root and is implemented with a queue that starts with the root and receives each visited node's children.

What is the time complexity of tree traversal?

Every standard traversal is O(n) in time because each node is visited once. Extra space is O(h) for depth-first traversal, where h is the tree's height, and O(w) for level order, where w is the widest level. A balanced tree has a height of about log n, while a chain has a height of n.

Can tree traversal be done without recursion?

Yes. Depth-first traversals can use an explicit stack in place of the call stack, and level order uses a queue. This avoids the recursion limit that can crash a recursive traversal on a very tall tree, such as a 5,000-node chain in Python, where CPython's default recursion limit is 1,000 and can be changed.

What does postorder traversal of an expression tree give?

Postorder traversal of an expression tree gives the postfix, or reverse Polish, form of the expression, in which each operator follows its two operands. For the tree of (3 + 4) × 5 it gives 3 4 + 5 followed by the multiply operator, which a stack evaluates to 35 with no brackets needed.

Next step

Rewrite the traversals from memory on a new tree, then compare the output of the recursive and iterative versions. If production Python and APIs are the next skills to build, see the Forward Deployed Engineer cohort from Leap by Masai. For the next data structure in this series, read about heaps and priority queues.