C++ binary search tree traversals

The concept

A binary search tree keeps smaller values in the left subtree and larger values in the right. A depth-first in-order traversal visits left, node, right, which yields the values in sorted order. A level-order traversal, also called breadth-first, visits all nodes of one depth before the next and uses a queue: pop a node, process it, and push its children.

These two orders answer different questions. In-order gives sorted output. Level order shows the shape of the tree and finds the shallowest node satisfying a condition first. Both visit every node once, so they take O(n) time. The recursion depth of the depth-first version equals the height of the tree.

Code example

#include <iostream>
#include <memory>
#include <queue>

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

void insert(std::unique_ptr<Node>& root, int value) {
  if (!root) {
    root = std::make_unique<Node>(value);
  } else if (value < root->value) {
    insert(root->left, value);
  } else if (value > root->value) {
    insert(root->right, value);
  }
}

void in_order(const Node* node) {
  if (node == nullptr) {
    return;
  }
  in_order(node->left.get());
  std::cout << " " << node->value;
  in_order(node->right.get());
}

void level_order(const Node* root) {
  std::queue<const Node*> pending;
  pending.push(root);
  while (!pending.empty()) {
    const Node* node = pending.front();
    pending.pop();
    std::cout << " " << node->value;
    if (node->left) pending.push(node->left.get());
    if (node->right) pending.push(node->right.get());
  }
}

int main() {
  std::unique_ptr<Node> root;
  for (int v : {50, 30, 70, 20, 40, 60, 80}) {
    insert(root, v);
  }
  std::cout << "in order:";
  in_order(root.get());
  std::cout << "\nlevel order:";
  level_order(root.get());
  std::cout << "\n";
}

in order: 20 30 40 50 60 70 80
level order: 50 30 70 20 40 60 80

Follow the code

Open the walkthrough to inspect the example one step at a time.

—

—

—

—

—

—

in order: 20 30 40 50 60 70 80
level order: 50 30 70 20 40 60 80

Behind the scenes

Cost and common mistakes

Both traversals are O(n). Level order needs O(w) extra space for the widest level w.

• level_order assumes the root is not null. Add a check for an empty tree.
• Deep recursion on a degenerate (chain-shaped) tree can overflow the stack.
• Pushing raw pointers into the queue is safe here because the tree outlives the traversal and the queue does not own the nodes.

Try it yourself

How would you print the tree height with level order?

Further reading

• C++ reference (cppreference) (external)
• C++ working draft (external)
• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) (external)