Pre-order traversal

O(n)

Pre-order traversal visits a node before its children: node, then left subtree, then right subtree. Because the root comes first, it's used to copy or serialize a tree (re-inserting in this order rebuilds it) and to print directory-like structures.

Binary search tree
Press ▶ to run
Edit the input and press Play

How it works

  1. Visit the current node first.
  2. Recurse into the left subtree.
  3. Recurse into the right subtree.
  4. The root always appears before its descendants.

Pseudocode

1preorder(node):                     # O(n)2  if node = null: return3  visit(node)                        # root before children4  preorder(node.left)5  preorder(node.right)