Tree Traversal Visualizer — Inorder, Preorder, Postorder, Level Order

How it works

1. Preorder: visit the node, then traverse its left subtree, then its right subtree.
2. Inorder: traverse the left subtree, visit the node, then traverse the right subtree.
3. Postorder: traverse the left subtree, then the right subtree, and visit the node last.
4. Level order: put the root in a queue; repeatedly take the front node, visit it and add its left and right children to the back.
5. In the depth-first orders the call stack remembers where to return; in level order the queue holds the nodes of the next level.

One tree, four orders

The visualizer opens on the tree built by inserting 60, 20, 70, 10, 40, 90, 30, 50, 80 into a binary search tree: 60 is the root with children 20 and 70; 10 and 40 hang under 20; 90 is 70's right child; 30 and 50 are 40's children; and 80 is 90's left child. Its four traversals:

• Preorder: 60, 20, 10, 40, 30, 50, 70, 90, 80
• Inorder: 10, 20, 30, 40, 50, 60, 70, 80, 90
• Postorder: 10, 30, 50, 40, 20, 80, 90, 70, 60
• Level order: 60, 20, 70, 10, 40, 90, 30, 50, 80

Look for the fingerprints: preorder always starts with the root, postorder always ends with it, inorder of a binary search tree comes out sorted, and level order reads the drawing row by row. Press each traversal above: blue nodes are calls still in progress (the call stack), and every visit flies into the output strip.

A trick for tracing traversals by hand

Draw a line around the tree, starting to the left of the root and hugging every node and edge counter-clockwise (an Euler tour). The line passes each node up to three times: on its left side, underneath it and on its right side.

• Write a node down on the first pass (its left side) → preorder.
• Write it down on the pass underneath → inorder.
• Write it down on the last pass (its right side) → postorder.

For level order, ignore the line and read the drawing top to bottom, left to right. This works for any binary tree, which makes it the fastest way to check an exam answer.

When to use each traversal

• Preorder — copying or serializing a tree (a parent is created before its children), printing folder hierarchies, prefix (Polish) notation. For a BST, inserting the preorder sequence into an empty tree rebuilds the exact same shape; this visualizer's share links rely on that.
• Inorder — reading a BST's keys in sorted order, validating a BST, finding the kth smallest key, and printing an expression tree in ordinary infix form.
• Postorder — anything where children must be finished before their parent: deleting or freeing a tree, computing heights, subtree sizes or sums, and evaluating an expression tree (its postorder is the postfix, or reverse Polish, form).
• Level order — anything about depth or distance from the root: printing level by level, minimum depth, the right-side view, linking nodes on the same level, and the level-by-level format LeetCode uses to write down trees.

Recursion, stacks and queues

The three depth-first traversals are three lines of recursion each. The call stack holds the path from the root to the current node, so they use O(h) extra space: O(log n) for a balanced tree, but O(n) for a degenerate one — deep enough to hit Python's default recursion limit of 1000. Iterative versions keep that stack explicitly: preorder pops a node, visits it and pushes its right child and then its left; inorder walks left pushing nodes, pops one, visits it and moves to its right child.

Level order is breadth-first search on a tree, and it needs a queue (first in, first out), not a stack: children are visited in the order they were discovered, so a whole level is finished before the next one starts. Its extra space is the width of the widest level — about n/2 for the bottom level of a perfect tree.

Morris traversal does inorder with O(1) extra space by temporarily pointing each left subtree's rightmost node back at its ancestor, then removing those threads on the way through.

Rebuilding a tree from its traversals

One traversal does not pin down a general binary tree, but the right pair does. With distinct keys, preorder + inorder (or postorder + inorder) gives a unique tree: the first preorder key (or the last postorder key) is the root, and its position in the inorder list splits the remaining keys into the left and the right subtree; repeat for each part.

Preorder + postorder is ambiguous whenever a node has a single child — nothing tells you whether that child is on the left or the right — unless the tree is full (every node has 0 or 2 children). For a binary search tree, preorder alone is enough, because the inorder sequence is simply the keys in sorted order.

Common mistakes

• Using a stack for level order: that produces a depth-first order, not level by level.
• Assuming postorder is preorder reversed. Reversing postorder gives node, right, left — a mirrored preorder. On the tree above, preorder is 60, 20, 10, … but reversed postorder is 60, 70, 90, ….
• Forgetting the base case if node is None: return, which crashes on the first missing child.
• Expecting sorted inorder output from any binary tree. That only holds for binary search trees.

Time and space complexity

Tree Traversal in Python

from collections import deque


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


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


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


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


# usage: out = []; inorder(root, out)    (level_order(root) returns a list)

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Binary Search Tree VisualizerBinary search tree visualizer: insert, search and delete keys step by step, see why every operation costs O(h), and compare a plain BST with AVL and B-trees.
• BFS Visualizer — Breadth-First SearchBreadth-first search explores a graph level by level with a queue and finds fewest-edge paths. Watch BFS run step by step, with code and O(V + E) analysis.
• DFS Visualizer — Depth-First SearchDepth-first search explores a graph by going as deep as possible, then backtracking. See DFS step by step with discovery and finish times, back edges and code.
• Stack & Queue VisualizerStack and queue visualizer: animate push, pop, enqueue and dequeue, compare LIFO with FIFO, and step through circular queues, deques and stack applications.
• BST Deletion — All Three CasesHow to delete a node from a binary search tree: the leaf, one-child and two-children cases, in-order successor or predecessor, with an animated example.
• AVL Tree VisualizerAVL tree visualizer: insert and delete keys, watch heights and balance factors update and LL, RR, LR, RL rotations keep every operation O(log n).