Binary Trees — Visual Learning

Preorder Traversal —
Visit before you dive.

Preorder visits the root before either child — Root, Left, Right. That single ordering choice is why it's the traversal used to serialize a tree to a string and rebuild it later: the root is always recorded before its descendants. Watch the root light up first at every recursive call on LearnBug, before the recursion has even looked at the children.

O(n)Time complexity
O(h)Space (call stack)
PythonLanguage

What is Preorder Traversal?

Visit the current node, then the left subtree, then the right subtree — recursively. For the tree 4(2(1,3),6) this visits 4, 2, 1, 3, 6. The root is always the first value printed for any subtree, which makes preorder a natural fit for recording tree shape.

Why visualization helps

It's easy to confuse preorder with inorder when you're only reading code — both are recursive DFS with three lines that look almost identical, just reordered. On LearnBug you watch exactly which line executes first at each call: print happens before either recursive call, not after.

YouTube — Preorder Traversal Explained Visually
📺 Drop your YouTube embed here
LearnBug — root visited before its children
🖼 Add a LearnBug screenshot here
Why Root First

Where preorder actually gets used

Serialization

Write the tree to a string root-first so parsing it back can rebuild parent-before-children, in one linear pass.

Tree → String

Cloning a tree

To rebuild an identical structure, you must create each parent node before you can attach its children — root-first order is required.

Deep copy

Prefix expression trees

In an expression tree, preorder produces prefix notation (Polish notation) — operator before its operands.

Prefix notation
Walkthrough

Preorder traversal on 4(2(1,3), 6)

1

preorder(4) visits the root immediately — before either child

Unlike inorder, there's no silent dive. The very first thing that happens is print(4), then the function calls preorder(4.left).

4visit
2
1
3
6
Output: [4]  |  Next: preorder(2)
2

preorder(2) visits itself, then dives left to node 1

print(2) happens before preorder(2.left) is even called. Node 1 is a leaf, so it visits and returns instantly.

4
2visit
1
3
6
Output: [4, 2, 1]  |  Next: preorder(2.right) → node 3
3

preorder(2)'s right call visits node 3 — node 2's subtree is done

Node 3 is a leaf, visits immediately. With both of node 2's children resolved, control returns up to node 4's right call.

4
2
1
3visit
6
Output: [4, 2, 1, 3]  |  Next: preorder(4.right) → node 6
4

preorder(6) visits the last node — traversal complete

Node 6 is a leaf under node 4's right side. It visits and returns, and the whole recursive call stack unwinds back to the original call.

4
2
1
3
6visit

Return: [4, 2, 1, 3, 6] ✓ every root printed before its own subtree

Python Code

Recursive and iterative preorder

PythonRecursive — O(n) time, O(h) space
def preorder(node, result):
    if node is None:
        return
    result.append(node.val)       # visit root FIRST
    preorder(node.left, result)   # then left
    preorder(node.right, result)  # then right
PythonIterative — explicit stack, same O(n) / O(h)
def preorder_iterative(root):
    if root is None:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)   # visit when popped
        # push right BEFORE left — stack pops left first
        if node.right: stack.append(node.right)
        if node.left:  stack.append(node.left)
    return result

Complexity Notes

TimeO(n)Every node visited exactly once
SpaceO(h)Recursion depth, or explicit stack size, equals tree height
Rebuild guaranteeRoot-firstThe first value in preorder output is always the root of that subtree
Iterative push orderRight, then LeftPushing right before left onto a stack ensures left pops out first

Frequently asked questions

Can I rebuild the original tree from just its preorder output?

Not from preorder alone if duplicate values are allowed and the tree isn't a BST — you need either the inorder sequence too, or extra markers for null children. If the tree is a BST, preorder alone is enough: each value's position relative to the running min/max bounds tells you where it belongs.

Why push right before left in the iterative version?

A stack is LIFO — last in, first out. To visit the left child before the right child (as preorder requires), the left child must be popped first, which means it must be pushed last. So the code pushes right, then left.

How is preorder different from BFS / level order?

Both visit the root early, but preorder is depth-first — it fully explores one entire subtree before moving to the sibling. Level order is breadth-first — it visits every node at depth 1 before any node at depth 2. They produce different orderings and use different data structures: recursion/stack for preorder, a queue for level order.

Does preorder work the same way on a non-BST binary tree?

Yes — preorder only depends on parent/child structure, not on any ordering property between values. It behaves identically on a BST or any other binary tree; only inorder's "sorted output" guarantee is BST-specific.

Watch the root light up before its children

Paste your preorder traversal into LearnBug and see the visit order animate live.

Open Playground →

Related topics

Inorder Traversal — sorted on a BST →BST Insertion — building the tree →Tree Height — recursive unwind →BFS vs DFS — Interview →