Preorder traversal

This is one of the common depth-first traversal orders for a binary tree. The crucial distinction is when the current node is processed relative to the left and right recursive calls.

Visit order

Root, then Left subtree, then Right subtree. For the example tree with A at the root, B and C below it, and D/E and F/G below those nodes, the complete order is:

A, B, D, E, C, F, G.

Every node is processed once. The relative position of output.Add or push_back in the code below is what changes the traversal order. The tree structure itself remains identical.

Step through the same tree

Visit order so far: –

Recursion stack: –

PreviousNext stepReset

Predict the next node before pressing Next step. Inorder depends on a defined left and right child.

Switch between preorder, inorder and postorder, predict the next highlighted node, then inspect the active recursion-call path. The displayed call stack represents the nested calls when each node is processed.

When to use this order

Preorder is useful when the parent must be processed before its descendants, such as emitting prefix notation or copying the tree structure. Unlike BFS, this algorithm follows a branch before its siblings, then returns to unfinished calls.

C# and C++ implementation

C#

C# | Preorder.cs

using System.Collections.Generic;

public sealed class Node
{
    public int Value { get; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
    public Node(int value) => Value = value;
}

static void Traverse(Node? node, List<int> output)
{
    if (node is null) return;
    output.Add(node.Value);
    Traverse(node.Left, output);
    Traverse(node.Right, output);
}

C++

C++ | Preorder.cpp

#include <memory>
#include <vector>

struct Node {
    int value;
    std::unique_ptr<Node> left, right;
    explicit Node(int value) : value(value) {}
};

void traverse(const Node* node, std::vector<int>& output) {
    if (!node) return;
    output.push_back(node->value);
    traverse(node->left.get(), output);
    traverse(node->right.get(), output);
}

Complexity and trade-offs

Both versions visit each of n nodes once, so time is O(n). Recursive auxiliary memory is O(h) where h is the tree height, because parent calls remain active. The output collection uses O(n) additional space; if you processed each value without saving results, that output allocation could be avoided. On a balanced binary tree, h is O(log n); on a skewed tree, h is O(n). A depth-first traversal is not inherently safe from deep recursion in a skewed structure.

Exercise: Write the traversal order for a tree with one root and only a right child. What changes if you move the output operation to a different position?

Continue with comparison of traversal orders and level-order BFS.

Reference: W3Schools preorder traversal.