Preorder Traversal, step by step.

Preorder traversal visits every node of a binary tree in the order node, left subtree, right subtree, so each node comes before all the nodes below it. It takes O(n) time for n nodes, recursively or with a stack in place of recursion. This page explains how it works, with a step-by-step animation from the VisiGrab app: preorder and its stack on a 15-node tree.

How preorder traversal works

What is preorder traversal? Root, left, right

Preorder traversal visits every node of a binary tree once, in the order node, left subtree, right subtree, often written NLR. The rule repeats inside every subtree, so each node comes before all the nodes below it, and its whole left subtree comes before its right one. That is the pre: a node is visited before its children. The name is also written pre-order or pre order.

Preorder is one of the three depth-first orders of a binary tree, with inorder and postorder. It is depth-first search from the root, left child first, without visited marks: only one link leads to each node, from its parent.

The order depends only on the tree's shape. Keys are never compared, so changing them leaves the order as it is. On a binary search tree (BST), preorder is not sorted in general: the root comes before the smaller keys of its left subtree.

Preorder traversal using a stack, without recursion

The app animates the iterative version. It keeps the nodes still to visit on a stack: push puts a node on top, and pop takes off the top one, the one pushed last.

1. Push the root: the stack starts with the root alone.

2. Pop and visit: take the top node off the stack and visit it.

3. Push the right child, then the left: push the popped node's children, skipping a missing one.

4. Repeat: go back to step 2 until the stack is empty. Each node is pushed once and popped once.

Why the right child is pushed first

A stack is last in, first out, so the child pushed last is popped next. The left child goes on last and is visited next, and the right child waits below it until the whole left subtree is done. Pushing the left child first would visit node, right, left: preorder's mirror image. With a queue in place of the stack, left child first, the same loop gives level order.

Preorder traversal pseudocode: recursive and iterative

The app's code has both versions; the names below drop the Traverse suffix of its listings. In pseudocode:

recursivePreOrder(node)
    if node is none
        return
    node.visit()
    recursivePreOrder(node.left)
    recursivePreOrder(node.right)

iterativePreOrder(root)
    if root is none
        return
    stack = empty stack
    stack.push(root)
    while stack is not empty
        node = stack.pop()
        node.visit()
        if node.right is not none
            stack.push(node.right)
        if node.left is not none
            stack.push(node.left)

recursivePreOrder stops at an empty link, none, and visits node before either call. That makes it preorder: node.visit() between the two calls would give inorder, and after them postorder. The calls still open form a hidden stack, the path from the root to node. iterativePreOrder keeps a stack of its own instead, holding the nodes still to visit, not the path: each pass of the while loop pops and visits one node and pushes its children. Both functions visit the nodes in the same order. In the app's Node class, visit() prints the key.

Preorder traversal example: the stack step by step

The player below runs the iterative version on the app's default tree, 15 nodes on four levels, with the stack on the right. Preorder visits 7, 24, 92, 1, 9, 11, 84, 53, 62, 76, 72, 33, 13, 32, 83. The dotted line leads from each visited node to the next, so it leaves the edges where the walk goes back to a waiting right child, as from the leaf 53 across to 62.

Preorder traversal with a stack

All steps as text
  1. Consider the iterative pre-order traversal. Use a stack to keep track of the nodes that need to be visited.
  2. Start with the root of the binary tree. Push this node onto the stack.
  3. Then pop the node (7) from the stack and visit it.
  4. First, push the right child of the visited node onto the stack.
  5. Then, push its left child onto the stack. After all children of the node (7) have been added, the next node (24) needs to be popped from the stack and visited.
  6. Pop the node (24) from the stack and visit it. Then repeat the procedure by pushing its child nodes onto the stack.
  7. Push the right child (11) onto the stack.
  8. Push the left child (92) onto the stack. Since all children of the node (24) have already been added, the next node (92) needs to be popped from the stack and visited.
  9. Pop the node (92) from the stack and visit it.
  10. Push the right child (9) onto the stack.
  11. Push the left child (1) onto the stack. Since all children of the node (92) have already been added, the next node (1) needs to be popped from the stack and visited.
  12. Pop the node (1) and visit it. Since it has no children, the next node (9) needs to be popped from the stack and visited.
  13. Pop the node (9) and visit it. Since it has no children, the next node (11) needs to be popped from the stack and visited.
  14. Pop the node (11) from the stack and visit it.
  15. Push the right child (53) onto the stack.
  16. Push the left child (84) onto the stack. Since all children of the node (11) have already been added, the next node (84) needs to be popped from the stack and visited.
  17. Pop the node (84) and visit it. Since it has no children, the next node (53) needs to be popped from the stack and visited.
  18. Pop the node (53) and visit it. Since it has no children, the next node (62) needs to be popped from the stack and visited.
  19. Pop the node (62) from the stack and visit it.
  20. Push the right child (13) onto the stack.
  21. Push the left child (76) onto the stack. Since all children of the node (62) have already been added, the next node (76) needs to be popped from the stack and visited.
  22. Pop the node (76) from the stack and visit it.
  23. Push the right child (33) onto the stack.
  24. Push the left child (72) onto the stack. Since all children of the node (76) have already been added, the next node (72) needs to be popped from the stack and visited.
  25. Pop the node (72) and visit it. Since it has no children, the next node (33) needs to be popped from the stack and visited.
  26. Pop the node (33) and visit it. Since it has no children, the next node (13) needs to be popped from the stack and visited.
  27. Pop the node (13) from the stack and visit it.
  28. Push the right child (83) onto the stack.
  29. Push the left child (32) onto the stack. Since all children of the node (13) have already been added, the next node (32) needs to be popped from the stack and visited.
  30. Pop the node (32) and visit it. Since it has no children, the next node (83) needs to be popped from the stack and visited.
  31. Pop the node (83) from the stack and visit it. If the stack is empty and this node has no descendants, it means that all nodes have already been visited, and the traversal is complete.
  32. Preorder visited the 15 nodes in the order 7, 24, 92, 1, 9, 11, 84, 53, 62, 76, 72, 33, 13, 32, 83: each node before its left subtree, and the left subtree before the right one.
Preorder traversal with a stack. Last step: Preorder visited the 15 nodes in the order 7, 24, 92, 1, 9, 11, 84, 53, 62, 76, 72, 33, 13, 32, 83: each node before its left subtree, and the left subtree before the right one.

Is preorder traversal depth-first search?

Yes: preorder is depth-first search from the root, left child first, recording each node when the search first reaches it. On a tree it needs no visited marks, because only one link leads to each node, from its parent.

What is the difference between preorder, inorder and postorder traversal?

Only when a node is visited: preorder visits it before its subtrees (node, left, right), inorder between them (left, node, right) and postorder after them (left, right, node). All three take O(n) time; the next section sets them beside level order.

Preorder vs inorder vs postorder and level order

The three depth-first orders follow the same route around the tree and differ only in when a node is visited: before its subtrees, between them or after them. Level order visits the tree one level at a time instead.

Postorder read backwards is node, right, left: the order this loop gives with the left child pushed first, which is why two stacks give postorder. This tree is not a binary search tree, so its inorder is not sorted; on a binary search tree it would be.

Preorder alone does not fix a tree's shape, but with distinct keys preorder and inorder together do: the first key in preorder is the root, and its place in the inorder splits the other keys into the two subtrees.

Preorder traversal time and space complexity

Preorder takes O(n) time for n nodes: each node is pushed and popped once, or gets one call. Extra space is O(h) for a tree of height h. The stack holds at most one waiting right child per level, plus the left child just pushed: h + 1 nodes, four on the player's tree of height 3. The recursion goes h + 2 calls deep, counting the calls on empty links. A balanced tree has a height in O(log n); a degenerate one, a chain, has a height of n − 1, so recursion needs O(n) extra space there. The iterative stack holds one node at a time on a chain, but a long left spine with a right child at every node fills it with about n/2 nodes, still O(n). Morris traversal gives preorder too, with no stack, in O(1) extra space.

Preorder traversal in Python, Java and C++

The app shows both versions in all three languages, with the Node class. Its code tab warns that recursion can overflow the call stack on a very deep tree; the iterative version avoids that.

Note

Java's ArrayDeque, which the app's code uses, rejects null, unlike the older Stack class, a Python list or C++'s std::stack. A version that pushes empty children and skips them when popped fails there; the app's listings push only the children that exist.

The full source code is on GitHub, in Python, Java and C++.

What is preorder traversal used for?

  • Copying a tree: each node is created before its children, so each copied subtree can hang straight from its new parent.
  • Serialization: the keys in preorder, with a marker for each empty link, store a tree as a flat list, and reading the list back in the same order rebuilds it.
  • Prefix (Polish) notation: the expression tree of (3 + 4) × 2 gives × + 3 4 2 in preorder; inorder gives its infix form and postorder its postfix form.
  • Hierarchies: on a tree with any number of children, preorder visits a node, then each child's subtree in turn. A folder listing that shows each folder above its contents is one.
  • Searching a tree that is not a BST: with no ordering rule to follow, any traversal may have to check all n nodes, in O(n).

Copying and serialization do not need preorder: postorder or level order with the same markers also rebuild a tree, though inorder with markers alone does not.

One tree here.
Build your own in the app.

In VisiGrab, preorder traversal walks the default tree or one you build, beside its stack, with a message for every push and pop.

Rebuild the tree

Custom opens a constructor with 15 node slots on four levels: add nodes and set their keys from 0 to 99, or delete a node with its whole subtree. The traversal then starts over on your tree.

Three more traversals

Inorder, postorder and level order run on the same default tree, each in its own color: postorder with two stacks, level order with a queue.

Why it is called preorder

The info dialog explains the name and lists copying, prefix notation and serialization, with the caveat that none of them is exclusive to preorder. Notes add that keys never change the order and why searching a tree that is not a BST costs O(n).

Recursive and iterative code

Both versions and the Node class in Python, Java and C++, with a warning that deep recursion can overflow the stack, a Java note recommending ArrayDeque, and a link to the full source on GitHub.

Quiz

Six questions, every option explained: the visit order, the name, why keys do not matter, which child is pushed first, what preorder suits, and why searching a non-BST costs O(n).

Stack, DFS and search trees

Stack has a topic of its own, Depth-First Search walks a graph with a stack that holds the path back to the start, and in Binary Search Tree you insert and delete keys yourself.

Visit the root
before its subtrees.

Download VisiGrab and step through preorder traversal on the default tree, or give the tree your own keys and shape and watch the stack choose the next node.

Preorder traversal is one of 30+ topics. See them all