Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Binary-tree traversals: four orders without recursion

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A binary-tree traversal is an ordering contract over node visits, not a property that automatically sorts values. Pre-order visits a node before its children, in-order visits between left and right subtrees, post-order visits after both, and level-order visits breadth first. This program uses explicit stacks for the three depth-first orders and a deque for breadth-first order, avoiding Python's recursion depth limit on a long chain. Post-order stores a ready flag so a node is emitted only after both descendants have been processed. The tree is not required to satisfy a binary-search ordering rule; an in-order walk is sorted only when the tree itself has that invariant.

Operational case

A task root T-47 has T-19 on the left and T-61 on the right; T-19 has T-07 and T-26 below it. Pre-order begins with T-47 and walks the left branch first. In-order visits T-07, T-19, T-26, T-47, then T-61. Post-order emits the leaves before their parent and ends at T-47. Level-order visits T-47, then T-19 and T-61, then the two lower tasks. These lists answer different operational questions: parent-first rendering, ordered-key inspection, dependency cleanup, and layer-by-layer work distribution.

Working Python program

python
"""Four traversal contracts for an arbitrary, non-search binary tree."""

from collections import deque
from dataclasses import dataclass


@dataclass
class TaskNode:
    task_id: str
    left: "TaskNode | None" = None
    right: "TaskNode | None" = None


def preorder(root):
    if root is None:
        return []
    pending = [root]
    result = []
    while pending:
        node = pending.pop()
        result.append(node.task_id)
        if node.right is not None:
            pending.append(node.right)
        if node.left is not None:
            pending.append(node.left)
    return result


def inorder(root):
    pending = []
    result = []
    current = root
    while pending or current is not None:
        while current is not None:
            pending.append(current)
            current = current.left
        current = pending.pop()
        result.append(current.task_id)
        current = current.right
    return result


def postorder(root):
    if root is None:
        return []
    pending = [(root, False)]
    result = []
    while pending:
        node, ready = pending.pop()
        if ready:
            result.append(node.task_id)
            continue
        pending.append((node, True))
        if node.right is not None:
            pending.append((node.right, False))
        if node.left is not None:
            pending.append((node.left, False))
    return result


def level_order(root):
    if root is None:
        return []
    pending = deque([root])
    result = []
    while pending:
        node = pending.popleft()
        result.append(node.task_id)
        if node.left is not None:
            pending.append(node.left)
        if node.right is not None:
            pending.append(node.right)
    return result


tasks = TaskNode("T-47", TaskNode("T-19", TaskNode("T-07"), TaskNode("T-26")), TaskNode("T-61"))
print(preorder(tasks))
print(inorder(tasks))
print(postorder(tasks))
print(level_order(tasks))

Output

Output
['T-47', 'T-19', 'T-07', 'T-26', 'T-61']
['T-07', 'T-19', 'T-26', 'T-47', 'T-61']
['T-07', 'T-26', 'T-19', 'T-61', 'T-47']
['T-47', 'T-19', 'T-61', 'T-07', 'T-26']

Time, space, and tradeoff

Each walk visits N nodes once and takes O(N) time, plus O(N) space for its returned list. The pre-, in-, and post-order working stacks use O(H) space for tree height H in this implementation; a degenerate chain can make H=N. The level-order queue uses O(W) working space for maximum level width W. Output storage is separate from working storage. The algorithms assume an acyclic, properly linked binary tree. If multiple parents share one mutable child or a cycle is introduced, these traversals may repeat work or fail to terminate without an additional visited-node policy.

Common Mistakes

  • Do not push a right child after a left child when a LIFO stack must visit left first.
  • Do not emit a post-order parent before both children finish.
  • Do not assume an arbitrary tree's in-order result is sorted.
  • Do not quote O(H) total memory while retaining an O(N) result list.

Connected lessons

Use this invariant in the dispatch audit project, then check the operations quiz.

data structures
range-query-structures
Storage details