C++UCS301
Trees & ApplicationsC++17

Tree Traversals

Preorder, inorder, postorder, and level order visit every node in different orders for different tasks.

Open this in the visual lab

What to understand

  • DFS traversal orders
  • Recursive and iterative forms
  • Level-order BFS
  • Expression-tree applications

Remember this

  1. 1Inorder of a BST is sorted
  2. 2Postorder is useful for deletion
  3. 3Level order uses a queue

Detailed notes

Depth-first traversals differ only in when the node is processed relative to its recursive subtrees: preorder before both, inorder between them, and postorder after both. The recursive structure directly mirrors the tree definition.

Level order is breadth-first and uses a queue. Iterative DFS replaces recursion with an explicit stack, which makes state and memory limits visible and permits custom traversal control.

How it works

  1. 1Return immediately for an empty subtree.
  2. 2Choose node-processing position from the desired order.
  3. 3For level order, enqueue children after visiting a node.
  4. 4Track explicit state when iterative postorder must distinguish entry from exit.

Worked trace

Traverse a seven-node perfect tree

Root 1; children 2,3; leaves 4,5,6,7
  1. 1Preorder processes node before children: 1,2,4,5,3,6,7.
  2. 2Inorder processes between children: 4,2,5,1,6,3,7.
  3. 3Postorder processes after children: 4,5,2,6,7,3,1.
  4. 4Level order uses a queue: 1,2,3,4,5,6,7.
Result: Same nodes, different processing semantics

Where it is used

  • Serialisation and tree copying with preorder
  • Sorted BST output with inorder
  • Deletion and expression evaluation with postorder

Common mistakes

  • Printing before the null check
  • Calling a DFS traversal BFS because output happens by levels on one example
  • Assuming recursion uses O(1) auxiliary space

Complexity analysis

OperationBestAverageWorstExtra space
TraversalO(n)O(n)O(n)O(h)

C++ implementation

C++17 reference
main.cpp

Recursive DFS and iterative level order

Each traversal visits every node once; the order changes the meaning of the output.

struct Node { int value; Node* left; Node* right; };

void inorder(Node* node) {
    if (!node) return;
    inorder(node->left);
    cout << node->value << ' ';
    inorder(node->right);
}

void levelOrder(Node* root) {
    if (!root) return;
    queue<Node*> pending;
    pending.push(root);
    while (!pending.empty()) {
        Node* node = pending.front(); pending.pop();
        cout << node->value << ' ';
        if (node->left) pending.push(node->left);
        if (node->right) pending.push(node->right);
    }
}
20 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.