Beginner · INTERACTIVE LESSON

Binary tree traversals

Compare preorder, inorder, postorder and level-order visits while following the active call stack or FIFO queue.

The interactive player is loading. If it does not appear, you can still read the explanation below.

THE IDEA BEHIND THE STEPS

How it works

A binary tree has one root and at most two ordered children per node: left and right. A null link means no child. Node IDs identify nodes; equal values do not merge them. This is not necessarily a binary search tree, so inorder does not promise sorted values.

Preorder visits a node before its left and right subtrees. Inorder visits after the left subtree and before the right. Postorder visits after both subtrees. Level-order visits breadth first using a queue, adding left before right. Change the traversal to compare the same tree from the beginning. The stack shows active DFS calls, including calls whose node has already been output but whose children are unfinished. Entering a call is not a visit: visits count only appends to the output.

Enter explicit root and nodes in JSON, with unique IDs of 1–8 ASCII letters, digits, underscores or hyphens, integer values -999–999 and both child fields set to an ID or null. At most 15 nodes are allowed. Every node must be reachable from the root exactly once: cycles, shared children, duplicate IDs and dangling links are rejected. Empty input is root null with nodes []. Editing the tree hides the old trace until valid input is applied.

For n nodes, all four traversals take O(n) time (O(1) for the empty tree). DFS uses O(h) auxiliary stack space with h the height in nodes; a skewed tree can have h=n. BFS uses O(w) auxiliary queue space with w the maximum level width. A queue can contain nodes from two adjacent levels, so its peak need not equal w. Each method outputs n IDs, using O(n) output space. These bounds exclude the input, validation, lookup/layout data and copied replay snapshots. The teaching engine uses constant-time map lookup and a FIFO queue with consumed entries removed; snapshot copies and drawing add overhead.

Visits count output appends only. Stack/queue size and peak count stored active frames or pending nodes, excluding the BFS node currently being visited. Each step explains push, return, enqueue, dequeue or visit; animation speed is not algorithm runtime. Reduced motion retains all states without movement.