Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Binary tree traversals: recursive and non-recursive

Definitions, algorithms, and Python implementations for recursive and non-recursive traversals of binary trees (preorder, inorder, postorder, level-order), with examples, complexities, and exam tips.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Binary tree traversals let us visit every node of a tree in a specific order. Engineers use traversals to evaluate expressions, serialize and deserialize trees, generate sorted sequences from Binary Search Trees (BSTs), and drive many algorithms in compilers, databases, and file systems.

Key ideas

  • Definition: A node stores a value (or key) and links to its children. An edge is a connection between a node and its child. A leaf is a node with no children. The root is the unique top node with no parent.
  • Definition: Height (of a node) is the length (number of edges) on the longest path from that node down to a leaf. Height of a tree is the height of its root. Depth of a node is the number of edges from the root to that node. Level of a node is depth + 1 (so the root is at level 1).
  • Definition: A traversal is an algorithm that visits every node exactly once in a specified order. For binary trees, the standard depth-first orders are preorder, inorder, and postorder; the standard breadth-first order is level-order.
  • Exact orders (Depth-First Search, DFS family):
    • Preorder: visit root, then traverse left subtree, then traverse right subtree.
    • Inorder: traverse left subtree, visit root, then traverse right subtree.
    • Postorder: traverse left subtree, traverse right subtree, then visit root.
  • Exact order (Breadth-First Search, BFS):
    • Level-order: visit nodes level by level from top to bottom, and within a level from left to right, typically using a queue.
  • Property used in other topics: In a Binary Search Tree (BST), an inorder traversal visits the keys in non-decreasing sorted order (if all keys are distinct, this order is strictly increasing; with duplicates, keys appear in non-decreasing order under a consistent duplicate-handling policy). This is often exploited to output sorted data without an extra sorting algorithm.
  • Recursion and stack behavior:
    • A recursive traversal expresses the problem on a tree in terms of the same problem on its subtrees, with a base case for an empty subtree.
    • Every recursive call is pushed on the call stack. The function returns when it finishes a subtree, popping the frame. Thus, recursion uses O(h) additional space where h is the tree height, because at most one active call per level exists.
  • Non-recursive (iterative) traversals simulate recursion using an explicit data structure:
    • Preorder, inorder, postorder use a stack.
    • Level-order uses a queue. Advanced note: Morris inorder/preorder traversals achieve O(1) extra space by temporarily 'threading' the tree (modifying/restoring pointers); use them only if allowed or specifically asked.
  • Time and space complexity basics:
    • Visiting each node once gives time complexity O(n) for all four traversals, where n is the number of nodes.
    • Additional space is O(h) for depth-first traversals (recursion stack or explicit stack), where h is height. For level-order, the queue may hold up to O(w) nodes where w is the maximum width of the tree (worst-case O(n)).
  • Null/empty cases and one-node cases:
    • The traversal of an empty tree produces an empty sequence.
    • For a single-node tree, all DFS traversals visit just that node; level-order does the same.
  • What to draw for diagrams in exams:
    • Draw a rooted binary tree with 6 nodes labeled A, B, C, D, E, F:
      • A at the top (root). Two children: left B and right C.
      • B has children: left D and right E (both leaves).
      • C has a right child F (leaf), and no left child.
    • Label edges clearly (left vs right). Mark the traversal order next to nodes as small numbers (1, 2, 3, …) for the chosen traversal; e.g., for preorder, number A=1, B=2, D=3, E=4, C=5, F=6.
  • Exact statements useful in exams:
    • Definition (Preorder traversal): For any binary tree T with root r, preorder(T) = visit r, then preorder(left(T)), then preorder(right(T)), with the base case preorder(∅) = ∅.
    • Definition (Inorder traversal): For any binary tree T with root r, inorder(T) = inorder(left(T)), visit r, then inorder(right(T)), with the base case inorder(∅) = ∅. In a BST, inorder yields keys in non-decreasing order under the BST ordering property.
    • Definition (Postorder traversal): For any binary tree T with root r, postorder(T) = postorder(left(T)), postorder(right(T)), then visit r, with the base case postorder(∅) = ∅.
    • Definition (Level-order traversal): A breadth-first traversal that visits nodes in increasing order of depth, from left to right within each level, commonly implemented with a FIFO queue.
    • Complexity law: For any of these traversals, if each node is visited a constant number of times and each visit costs O(1), the total running time is O(n). The auxiliary space is O(h) for DFS and up to O(n) for BFS on degenerate level widths.

Formulas

  • T: a binary tree (unit: not applicable). Applies when defining preorder recursively. · means sequence concatenation.
  • inorder(T) = inorder(left(T)) · [root(T)] · inorder(right(T))
    • T: a binary tree (unit: not applicable). Applies when defining inorder recursively.
  • postorder(T) = postorder(left(T)) · postorder(right(T)) · [root(T)]
    • T: a binary tree (unit: not applicable). Applies when defining postorder recursively.
  • Time(DFS traversals) = O(n); Space(DFS traversals) = O(h)
    • n: number of nodes (unit: count), h: height (unit: edges). Applies for preorder/inorder/postorder recursive or stack-based.
  • Time(level-order) = O(n); Space(level-order) = O(w)
    • n: number of nodes (count), w: maximum width (count). Applies when using a queue for BFS.
  • Python syntax reminders (commonly needed):
    • class Node: def __init__(self, key, left=None, right=None): ...
    • def func(node): if node is None: return ...
    • stack.append(x) (push), stack.pop() (pop from end)
    • from collections import deque; q = deque(); q.append(x); x = q.popleft()
    • List building: out = []; out.append(val); return out

Worked examples

Example 1: Recursive traversals on a given binary tree

  • Tree (draw as described under Key ideas):
    • Root A; left child B, right child C; B has children D (left) and E (right); C has right child F.
  • Expected traversal sequences:
    • Preorder (root, left, right): A, B, D, E, C, F
    • Inorder (left, root, right): D, B, E, A, C, F
    • Postorder (left, right, root): D, E, B, F, C, A
    • Level-order (BFS): A, B, C, D, E, F
  • Python program (complete, runs):
from collections import deque

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

def preorder_recursive(node, out):
    if node is None:
        return
    out.append(node.key)
    preorder_recursive(node.left, out)
    preorder_recursive(node.right, out)

def inorder_recursive(node, out):
    if node is None:
        return
    inorder_recursive(node.left, out)
    out.append(node.key)
    inorder_recursive(node.right, out)

def postorder_recursive(node, out):
    if node is None:
        return
    postorder_recursive(node.left, out)
    postorder_recursive(node.right, out)
    out.append(node.key)

def level_order(node):
    out = []
    if node is None:
        return out
    q = deque([node])
    while q:
        cur = q.popleft()
        out.append(cur.key)
        if cur.left:
            q.append(cur.left)
        if cur.right:
            q.append(cur.right)
    return out

# Build sample tree
#        A
#       / \
#      B   C
#     / \   \
#    D   E   F
D = Node('D')
E = Node('E')
F = Node('F')
B = Node('B', D, E)
C = Node('C', None, F)
A = Node('A', B, C)

pre, ino, post = [], [], []
preorder_recursive(A, pre)
inorder_recursive(A, ino)
postorder_recursive(A, post)
level = level_order(A)

print('Preorder:', ' '.join(pre))
print('Inorder:', ' '.join(ino))
print('Postorder:', ' '.join(post))
print('Level-order:', ' '.join(level))

Sample input:

  • (none; the program builds the fixed tree in code) Sample output:
Preorder: A B D E C F
Inorder: D B E A C F
Postorder: D E B F C A
Level-order: A B C D E F

Example 2: Non-recursive (iterative) DFS traversals using a stack, and BFS using a queue

  • We use the same tree as Example 1 to verify that recursive and iterative outputs match.
  • Python program (complete, runs):
from collections import deque

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

def preorder_iterative(root):
    if root is None:
        return []
    out = []
    stack = [root]
    while stack:
        node = stack.pop()
        out.append(node.key)
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

def inorder_iterative(root):
    out = []
    stack = []
    cur = root
    while cur is not None or stack:
        # Go to leftmost
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.key)
        # Visit right subtree
        cur = cur.right
    return out

def postorder_iterative_two_stacks(root):
    if root is None:
        return []
    s1, s2 = [root], []
    while s1:
        node = s1.pop()
        s2.append(node)
        if node.left:
            s1.append(node.left)
        if node.right:
            s1.append(node.right)
    out = [node.key for node in reversed(s2)]
    return out

def level_order(root):
    out = []
    if root is None:
        return out
    q = deque([root])
    while q:
        node = q.popleft()
        out.append(node.key)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return out

# Build the same sample tree
D = Node('D')
E = Node('E')
F = Node('F')
B = Node('B', D, E)
C = Node('C', None, F)
A = Node('A', B, C)

print('Preorder (iter):', ' '.join(preorder_iterative(A)))
print('Inorder (iter):', ' '.join(inorder_iterative(A)))
print('Postorder (iter):', ' '.join(postorder_iterative_two_stacks(A)))
print('Level-order (iter):', ' '.join(level_order(A)))

Sample input:

  • (none; the program builds the fixed tree in code) Sample output:
Preorder (iter): A B D E C F
Inorder (iter): D B E A C F
Postorder (iter): D E B F C A
Level-order (iter): A B C D E F

Example 3: Theory model answer — Derive time and space complexity for recursive inorder traversal

  • Question: State and derive the time and space complexity of the recursive inorder traversal of a binary tree with n nodes and height h. State the assumptions.
  • Model answer (step-by-step):
    1. Assumptions: Each visit to a node (processing the key and pointer moves) takes O(1) time; pointer dereferences are O(1); recursion overhead per call is O(1). The tree has n nodes and height h.
    2. Recurrence for time T(n): Each node is processed once and makes at most two recursive calls on its left and right subtrees. The total work sums to c per node for some constant c. Hence T(n) = c·n = O(n).
    3. Space: At any moment the recursion stack contains at most one activation per level along a root-to-leaf path. Therefore the maximum depth of simultaneous calls equals h + 1 frames (including the leaf/base). Thus auxiliary space is O(h). For a perfectly balanced tree, h = ⌊log2(n)⌋; for a skewed tree, h = n − 1. Therefore, best case O(log n) space, worst case O(n) space.
    4. Conclusion: Recursive inorder traversal runs in O(n) time and uses O(h) auxiliary space, where h is the height of the tree.

Common mistakes

  • Mixing up left and right pushes in iterative preorder. If you push left before right, the right subtree may be processed first because of LIFO order.
  • In iterative inorder, forgetting to continue with the right child after popping leads to missing nodes.
  • For postorder using one stack, mishandling the last visited pointer causes duplicate visits; to avoid complexity in exams, prefer the two-stack method unless specifically asked otherwise.
  • Confusing DFS and BFS — writing a stack-based algorithm when the question asks for level-order (which needs a queue).
  • Writing asymptotic space as O(n) for all DFS traversals without noting it is actually O(h) in general; O(n) only in the worst case when the tree is skewed.
  • For BST-related questions, claiming preorder or postorder give sorted order; only inorder is sorted (under the BST property).
  • Not labeling diagrams with left/right child distinctly; examiners deduct marks if the constructed traversal order does not match the drawn tree.

For your exam

  • Short notes: Recursive vs iterative traversals; time and space complexity; uses of each traversal (expression tree evaluation uses postorder; BST inorder produces sorted keys; serialization often uses preorder/level-order).
  • Derivations/Proof-style: Show O(n) time by summing constant work per node; show O(h) auxiliary space by arguing maximum call stack depth; relate h to n for balanced vs skewed trees.
  • Programs: Python or C programs for all four traversals. For postorder, either two stacks or one stack with a last-visited pointer. Include correct base cases, proper use of stack/queue, and show sample outputs.
  • Diagrams: Draw a clear binary tree with labeled left/right, and annotate visit order numbers for the requested traversal. If asked to “trace” an algorithm, show the content of the stack/queue at 2–3 key steps.
  • What gets full marks: Correct algorithm/order, correct handling of empty tree, correct complexity statements, clean and readable code/steps, correct and consistent outputs that match the diagram, and a brief note on space usage.

Quick check

  1. For a BST, which traversal yields the keys in non-decreasing sorted order? Why?
  2. What additional data structure does level-order traversal use, and what is its worst-case auxiliary space in big-O terms?
  3. State the time complexity and the auxiliary space complexity (in terms of n and h) for recursive preorder traversal.

Answers: 1) Inorder, because it visits left subtree (all smaller keys), then root, then right subtree (all larger keys) per the BST property. 2) A FIFO queue; O(n) in the worst case (when a level holds O(n) nodes). 3) Time O(n); auxiliary space O(h), where h is the tree height.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?