SimuVedaAlgorithms Lab Open in the lab

Trees / Beginner

Preorder Traversal Visualizer

The node first, then its left subtree, then its right subtree.

Start the Preorder Traversal simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(h)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Preorder traversal: left subtree, right subtree and the node itself, in the order shown in the code.
  2. At node 50.
  3. Visit 50.
  4. Go left from 50.
  5. At node 30.
  6. Visit 30.
  7. Go left from 30.
  8. At node 20.
  9. Visit 20.
  10. Back at 30.
  11. Go right from 30.
  12. At node 40.
  13. Visit 40.
  14. Go left from 40.
  15. At node 35.
  16. Visit 35.
  17. Back at 40.
  18. Back at 30.
  19. Back at 50.
  20. Go right from 50.
  21. … 12 more steps …
  22. Visit 80.
  23. Back at 70.
  24. Back at 50.
  25. Done. Visit order: 50, 30, 20, 40, 35, 70, 60, 65, 80.

Try it with your own input →

Preorder traversal in Java, Python, C++, C and JavaScript

void preorder(Node n) {
  if (n == null) return;
  visit(n);
  preorder(n.left);
  preorder(n.right);
}
def preorder(n):
    if n is None:
        return
    visit(n)
    preorder(n.left)
    preorder(n.right)
void preorder(Node* n) {
  if (!n) return;
  visit(n);
  preorder(n->left);
  preorder(n->right);
}
void preorder(struct Node* n) {
  if (n == NULL) return;
  visit(n);
  preorder(n->left);
  preorder(n->right);
}
function preorder(n) {
  if (n === null) return;
  visit(n);
  preorder(n.left);
  preorder(n.right);
}

In an interview

Preorder is used to copy or serialize a tree. Rebuilding a BST from its preorder gives the same shape.

More trees