Binary Tree Traversals: short notes (Data Structures)

Revision mode

Introduction

A traversal visits every node of a tree exactly once, in some systematic order. For a binary tree there are three natural depth-first orders, distinguished only by when the root is visited relative to its two subtrees, plus the breadth-first level order. Traversals are the basis of almost every tree algorithm: printing, copying, freeing, computing height or size, evaluating expression trees, and checking BST order.

This note defines the four traversals, gives recursive and iterative implementations with their costs, and shows the standard derived computations. Which combinations of traversals determine a tree uniquely, and how to rebuild a tree from preorder and inorder, are covered in Trees and Binary Trees.

Conventions: C11; a tree is a pointer to its root node, and NULL is the empty tree. Height of the empty tree is $-1$ and of a single node is 0, as in the trees note. The code walks pointer-linked nodes (left, right). When an array representation appears in a question, state whether it is 0-based or 1-based before indexing.

Prerequisites

Trees and Binary Trees: terminology, linked representation.
Recursion: recursive calls, winding and unwinding.

Core concepts

The four orders

Traversal	Order at each node	Mnemonic
Preorder	root, left subtree, right subtree	NLR
Inorder	left subtree, root, right subtree	LNR
Postorder	left subtree, right subtree, root	LRN
Level order	level 0 left to right, then level 1, and so on	breadth first

Running example (nodes are letters):

Text

          A
        /   \
       B     C
      / \     \
     D   E     F
        /
       G

Traversal	Result
Preorder	A B D E G C F
Inorder	D B G E A C F
Postorder	D G E B F C A
Level order	A B C D E F G

Preorder, inorder, postorder and level order on one tree — Figure 1. The running example tree traced by an Euler tour (a walk around the outside of the tree, keeping the tree on the left). A node is listed in preorder when the tour first passes it on the left, in inorder when it passes underneath, and in postorder when it passes on the right. Level order reads the tree row by row.

Quick facts. The root is the first node in preorder and the last in postorder. The leftmost node (follow left links from the root) is first in inorder. Leaves appear in the same relative order (left to right) in preorder, inorder and postorder.

Recursive implementations

struct tnode { char key; struct tnode *left, *right; };

void pre(const struct tnode *t)  { if (!t) return; visit(t); pre(t->left);  pre(t->right); }
void in(const struct tnode *t)   { if (!t) return; in(t->left);  visit(t); in(t->right);  }
void post(const struct tnode *t) { if (!t) return; post(t->left); post(t->right); visit(t); }

The three differ only in where visit sits, exactly like printing before or after a recursive call in Recursion.

Cost. Each node is visited once: $\Theta(n)$ time. The recursion depth is at most $h + 1$ frames for the nodes plus one for a NULL call, so the stack space is $O(h)$ : $O(\lg n)$ for a balanced tree, $O(n)$ for a skewed one. A recursive traversal that recurses into NULL children makes exactly $2n + 1$ calls on an $n$ -node tree: one per node plus one per null link, and a binary tree with $n$ nodes has $n + 1$ null links (Trees and Binary Trees).

How it works: iterative traversals

Recursion uses the call stack implicitly; with an explicit stack the same traversals run iteratively.

Iterative inorder

void in_iter(const struct tnode *t) {
    const struct tnode *st[MAXH]; int top = -1;   /* MAXH >= height + 1; this array reserves Theta(MAXH) pointers */
    while (t || top >= 0) {
        while (t) { st[++top] = t; t = t->left; } /* go as far left as possible */
        t = st[top--];                            /* the leftmost unvisited node */
        visit(t);
        t = t->right;                             /* then its right subtree */
    }
}

The shown fixed array uses $\Theta(\text{MAXH})$ storage; this is $O(h+1)$ only when $\text{MAXH}=\Theta(h+1)$ . An appropriately sized dynamic/abstract stack uses $O(h+1)$ . The stack holds the path of nodes whose left subtree is being processed, so it never holds more than $h + 1$ nodes. On the running example it reaches 3 nodes twice: A, B, D (before D is visited) and A, E, G (before G is visited).

Iterative preorder

Push the root; repeatedly pop a node, visit it, and push its right child then its left child (so the left is popped first).

Iterative postorder

One simple method uses the preorder idea with the children pushed in the opposite order (left, then right), which produces root, right, left; reversing that sequence gives left, right, root, the postorder. The reversal needs a second stack or an output array.

Level order with a queue

void level(const struct tnode *t) {
    const struct tnode *q[MAXN]; int f = 0, r = 0;  /* MAXN: at least the number of nodes */
    if (t) q[r++] = t;
    while (f < r) {
        const struct tnode *x = q[f++];
        visit(x);
        if (x->left)  q[r++] = x->left;
        if (x->right) q[r++] = x->right;
    }
}

Level order is breadth-first search on a tree (Queues, Breadth-First Search). An appropriately implemented live-entry abstract queue uses $O(w)$ space, where $w$ is maximum level width. The displayed C code instead reserves q[MAXN] with monotone indices: it uses $\Theta(\mathrm{MAXN})$ auxiliary space, or $\Theta(n)$ when MAXN is proportional to n. It requires MAXN to hold every node, not merely the widest level.

Summary of costs

Traversal	Time	Extra space
Recursive pre, in, post	$\Theta(n)$	$O(h)$ call stack
Iterative with a stack	$\Theta(n)$	$O(h+1)$ abstract/dynamic stack; shown array $\Theta(\text{MAXH})$ (postorder by reversal: $O(n)$ )
Level order	$\Theta(n)$	abstract live-entry queue: $O(w)$ ; displayed array: $\Theta(\mathrm{MAXN})$

$O(1)$ -extra-space traversals exist (threaded trees and Morris traversal temporarily reuse null links); the idea is that the $n + 1$ null links can point to inorder predecessors or successors.

Computations built on traversals

Most tree functions are a postorder computation: combine the answers for the subtrees, then compute the node's own answer.

int size(const struct tnode *t)   { return t ? 1 + size(t->left) + size(t->right) : 0; }
int height(const struct tnode *t) {                        /* empty tree: -1 */
    if (!t) return -1;
    int a = height(t->left), b = height(t->right);
    return 1 + (a > b ? a : b);
}
int leaves(const struct tnode *t) {
    if (!t) return 0;
    if (!t->left && !t->right) return 1;
    return leaves(t->left) + leaves(t->right);
}
void freet(struct tnode *t) { if (!t) return; freet(t->left); freet(t->right); free(t); }

Freeing is naturally postorder in the shown implementation. A parent may also be freed before its descendants if its child pointers are saved first; never read those pointers through the freed parent.
Copying a tree is naturally preorder: create the node, then copy the subtrees.
BST check: a binary tree is a binary search tree exactly when its inorder sequence is strictly increasing (for distinct keys); see Binary Search Trees.

Expression trees

In an expression tree, leaves are operands and internal nodes are operators. For $(a + b) * (c - d)$ :

Traversal	Result	Notation
Preorder	`* + a b - c d`	prefix
Inorder	`a + b * c - d`	infix without parentheses (ambiguous)
Postorder	`a b + c d - *`	postfix

Evaluating the tree is a postorder computation; this is the link to Stack Applications. Fully parenthesised infix requires printing ( before the left subtree and ) after the right subtree of every operator node.

Worked examples

C outputs below are for C11 with gcc on x86-64 Linux (LP64).

Example 1. On the running example, the recursive functions print ABDEGCF, DBGEACF, DGEBFCA; level order prints ABCDEFG; iterative inorder prints DBGEACF.

Example 2. size is 7, height is 3 (path A, B, E, G), leaves is 3 (D, G, F), and a traversal that recurses into null children makes $2 \cdot 7 + 1 = 15$ calls.

Example 3. The expression tree for $(a+b)*(c-d)$ gives *+ab-cd, a+b*c-d and ab+cd-*.

Example 4 (reading a traversal backwards). Given preorder A B D E G C F and inorder D B G E A C F: A is the root; in the inorder, D B G E lie to its left and C F to its right; recursing rebuilds the running example. The full method is in Trees and Binary Trees.

Important properties and observations

All four traversals are $\Theta(n)$ time.
Depth-first traversals need $O(h)$ stack. Level order uses $O(w)$ with a live-entry queue; the displayed fixed-array implementation reserves $\Theta(\mathrm{MAXN})$ , not merely $O(w)$ .
Preorder: root first. Postorder: root last. Inorder of a BST: sorted.
Leaves keep their left-to-right order in all three depth-first traversals.
A recursive traversal makes $2n + 1$ calls if it calls on null children, $n$ if it checks children before calling.
Inorder alone, preorder alone or postorder alone does not determine the tree; inorder together with preorder or postorder does (distinct keys).

GATE examination perspective

Write the traversal of a drawn tree, or draw the tree from two traversals.
Output of a modified traversal (for example, printing twice, or visiting right before left): trace the recursion.
Count calls or stack depth of a recursive traversal.
Expression trees: prefix, infix and postfix forms.
Which traversal suits a task: postorder to free or evaluate, inorder to get sorted BST keys, level order for shortest path in edges from the root.

Summary

Sources

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009: Section 10.4 (representing rooted trees; Exercises 10.4-2, 10.4-3 and 10.4-5 on recursive, stack-based and constant-space traversals), Section 12.1 (inorder tree walk).
D. E. Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., Addison-Wesley, 1997: Section 2.3.1 (traversing binary trees, threaded trees).