6.4. The Binary Tree ADT

Unlike the linear sequences covered so far, a tree is a hierarchical abstract data type. Conceptually, it can be thought of as a collection of nodes defined by parent-child relationships.

Refer to Tree ADT concepts to review the basic vocabulary and structure of binary trees.

So far, we have discussed trees only at a conceptual level. In this section we will program one.

In a binary tree, one node is the root. It serves as the 'trunk' of the tree and serves the same function as the head of a list The root node is the only node in a tree without a parent. All other nodes in a tree refer to exactly 1 parent. In a binary tree, the children are commonly referred to as the left and right children.

A simple binary tree can be implemented as a recursive data structure:

A simple recursive tree

template <class T>
 struct tree {
    T value;
    tree<T>* left = nullptr;
    tree<T>* right = nullptr;
};

This tree stores a single value of type T and has two pointers to potential children. It is important to remember when working with a recursive tree such as this that a child might be a nullptr.

6.4.1. Binary tree traversal

Traversal of a data structure means visit elements of the structure. It might mean visiting a subset, but can also involve visiting each element from the first to last.

For sequential containers, identifying the start and end of the container is simple. But where are the first and last elements of a tree?

The short answer is that there is no single answer. Since a tree is not a sequential data structure, a tree allows for different sequences (or traversals). There are several different types of traversals. The most common tree traversals are:

• Preorder

• Postorder

• Inorder

• Level order

Given the following binary tree, let's implement functions that traverse the tree using each of the four methods.

In each traversal deck, the node indicator identifies the current node. The printed sequence beneath the tree grows whenever a value is visited. Moving the indicator during recursive descent or return does not always print a value; the traversal determines when to visit it. Calls for missing children return without printing. Level order uses a queue to choose the next node.

Subject of the next 4 traversals

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

6.4.1.1. Preorder traversal

A depth first traversal.

Visit all nodes before visiting children:

Preorder

In this generic code block, the function visit represents the action to take on the current node.

void preorder(tree<T>* node) {
  if (node == nullptr) {
    return;
  }
  visit(node);
  preorder(node->left);
  preorder(node->right);
}

Preorder traversal: print the node, traverse left, then traverse right

Card 1: Print the root, a.

Start at the root, a. Print a before traversing its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: a

Card 2: Descend to b; print b.

Move from a to its left child, b. Print b before traversing its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“b” is highlighted.

Indicator “node” points to “b”.

Printed: a b

Card 3: Descend to d; print d.

Move from b to its right child, d. Print d before traversing its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“d” is highlighted.

Indicator “node” points to “d”.

Printed: a b d

Card 4: Return from d to b.

The call for d has returned to b, completing b's right subtree. b was printed before its children; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“b” is highlighted.

Indicator “node” points to “b”.

Printed: a b d

Card 5: Return from b to a.

The call for b has returned to a, completing a's left subtree. a was printed before its children; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: a b d

Card 6: Descend to c; print c.

Move from a to its right child, c. Print c before traversing its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: a b d c

Card 7: Descend to e; print e.

Move from c to its left child, e. Print e before traversing its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“e” is highlighted.

Indicator “node” points to “e”.

Printed: a b d c e

Card 8: Descend to g; print g.

Move from e to its left child, g. Print g before traversing its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“g” is highlighted.

Indicator “node” points to “g”.

Printed: a b d c e g

Card 9: Return from g to e.

The call for g has returned to e, completing e's left subtree. e was printed before its children; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“e” is highlighted.

Indicator “node” points to “e”.

Printed: a b d c e g

Card 10: Return from e to c.

The call for e has returned to c, completing c's left subtree. c was printed before its children; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: a b d c e g

Card 11: Descend to f; print f.

Move from c to its right child, f. Print f before traversing its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: a b d c e g f

Card 12: Descend to h; print h.

Move from f to its left child, h. Print h before traversing its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“h” is highlighted.

Indicator “node” points to “h”.

Printed: a b d c e g f h

Card 13: Return from h to f.

The call for h has returned to f, completing f's left subtree. f was printed before its children; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: a b d c e g f h

Card 14: Descend to i; print i.

Move from f to its right child, i. Print i before traversing its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“i” is highlighted.

Indicator “node” points to “i”.

Printed: a b d c e g f h i

Card 15: Return from i to f.

The call for i has returned to f, completing f's right subtree. f was printed before its children; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: a b d c e g f h i

Card 16: Return from f to c.

The call for f has returned to c, completing c's right subtree. c was printed before its children; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: a b d c e g f h i

Card 17: Return from c to a.

The call for c has returned to a, completing a's right subtree. a was printed before its children; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: a b d c e g f h i

Card 18: Preorder traversal is complete.

The call for the root has returned. Every node has been printed once. The node indicator has no current target.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

Indicator “node” has no target.

Printed: a b d c e g f h i

Run It

#include <iostream>

template <class T>
void print(tree<T>* node) {
  if (node == nullptr) {
    return;
  }
  std::cout << node->value << ' ';
  print(node->left);
  print(node->right);
}

int main() {
  std::cout << "Preorder: ";
  print(make_tree());

  return 0;
}

6.4.1.2. Postorder traversal

A depth first traversal.

Visit all nodes after visiting children:

Postorder

void postorder(tree<T>* node) {
  if (node == nullptr) {
    return;
  }
  postorder(node->left);
  postorder(node->right);
  visit(node);
}

Postorder traversal: traverse left, traverse right, then print the node

Card 1: Start at a.

Start at the root, a. Traverse the children before printing a. The call for a waits for both subtrees to finish.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: (none)

Card 2: Descend to b.

Move from a to its left child, b. Traverse the children before printing b. The call for b waits for both subtrees to finish.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“b” is highlighted.

Indicator “node” points to “b”.

Printed: (none)

Card 3: Descend to d; print d.

Move from b to its right child, d. d is a leaf. Both child calls return immediately, so print d.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“d” is highlighted.

Indicator “node” points to “d”.

Printed: d

Card 4: Return to b; print b.

The call for d has returned to b, completing b's right subtree. Both subtrees are complete, so print b after its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“b” is highlighted.

Indicator “node” points to “b”.

Printed: d b

Card 5: Return from b to a.

The call for b has returned to a, completing a's left subtree. The right subtree still needs to be traversed. Keep a unprinted until that subtree returns.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: d b

Card 6: Descend to c.

Move from a to its right child, c. Traverse the children before printing c. The call for c waits for both subtrees to finish.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: d b

Card 7: Descend to e.

Move from c to its left child, e. Traverse the children before printing e. The call for e waits for both subtrees to finish.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“e” is highlighted.

Indicator “node” points to “e”.

Printed: d b

Card 8: Descend to g; print g.

Move from e to its left child, g. g is a leaf. Both child calls return immediately, so print g.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“g” is highlighted.

Indicator “node” points to “g”.

Printed: d b g

Card 9: Return to e; print e.

The call for g has returned to e, completing e's left subtree. Both subtrees are complete, so print e after its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“e” is highlighted.

Indicator “node” points to “e”.

Printed: d b g e

Card 10: Return from e to c.

The call for e has returned to c, completing c's left subtree. The right subtree still needs to be traversed. Keep c unprinted until that subtree returns.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: d b g e

Card 11: Descend to f.

Move from c to its right child, f. Traverse the children before printing f. The call for f waits for both subtrees to finish.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: d b g e

Card 12: Descend to h; print h.

Move from f to its left child, h. h is a leaf. Both child calls return immediately, so print h.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“h” is highlighted.

Indicator “node” points to “h”.

Printed: d b g e h

Card 13: Return from h to f.

The call for h has returned to f, completing f's left subtree. The right subtree still needs to be traversed. Keep f unprinted until that subtree returns.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: d b g e h

Card 14: Descend to i; print i.

Move from f to its right child, i. i is a leaf. Both child calls return immediately, so print i.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“i” is highlighted.

Indicator “node” points to “i”.

Printed: d b g e h i

Card 15: Return to f; print f.

The call for i has returned to f, completing f's right subtree. Both subtrees are complete, so print f after its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: d b g e h i f

Card 16: Return to c; print c.

The call for f has returned to c, completing c's right subtree. Both subtrees are complete, so print c after its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: d b g e h i f c

Card 17: Return to a; print a.

The call for c has returned to a, completing a's right subtree. Both subtrees are complete, so print a after its children.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: d b g e h i f c a

Card 18: Postorder traversal is complete.

The call for the root has returned. Every node has been printed once. The node indicator has no current target.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

Indicator “node” has no target.

Printed: d b g e h i f c a

Run It

The only difference between the preorder example and this is the order of the function calls in the print function.

#include <iostream>

template <class T>
void print(tree<T>* node) {
  if (node == nullptr) {
    return;
  }
  print(node->left);
  print(node->right);
  std::cout << node->value << ' ';
}

int main() {
  std::cout << "Postorder: ";
  print(make_tree());

  return 0;
}

6.4.1.3. Inorder traversal

A depth first traversal.

Visit the left child (and the left child subtree), then visit the current node, then visit the right child (and the right child subtree),

Inorder

void inorder(tree<T>* node) {
  if (node == nullptr) {
    return;
  }
  inorder(node->left);
  visit(node);
  inorder(node->right);
}

Inorder traversal: traverse left, print the node, then traverse right

Card 1: Start at a.

Start at the root, a. The call for a waits while its left subtree is traversed. Its value will be printed after that subtree returns.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: (none)

Card 2: Descend to b; print b.

Move from a to its left child, b. b has no left child, so its left-subtree call returns immediately. Print b before traversing its right subtree.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“b” is highlighted.

Indicator “node” points to “b”.

Printed: b

Card 3: Descend to d; print d.

Move from b to its right child, d. d has no left child, so its left-subtree call returns immediately. Print d before traversing its right subtree.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“d” is highlighted.

Indicator “node” points to “d”.

Printed: b d

Card 4: Return from d to b.

The call for d has returned to b, completing b's right subtree. b was printed before its right subtree; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“b” is highlighted.

Indicator “node” points to “b”.

Printed: b d

Card 5: Return to a; print a.

The call for b has returned to a, completing a's left subtree. Print a now, between its left and right subtrees.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: b d a

Card 6: Descend to c.

Move from a to its right child, c. The call for c waits while its left subtree is traversed. Its value will be printed after that subtree returns.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: b d a

Card 7: Descend to e.

Move from c to its left child, e. The call for e waits while its left subtree is traversed. Its value will be printed after that subtree returns.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“e” is highlighted.

Indicator “node” points to “e”.

Printed: b d a

Card 8: Descend to g; print g.

Move from e to its left child, g. g has no left child, so its left-subtree call returns immediately. Print g before traversing its right subtree.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“g” is highlighted.

Indicator “node” points to “g”.

Printed: b d a g

Card 9: Return to e; print e.

The call for g has returned to e, completing e's left subtree. Print e now, between its left and right subtrees.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“e” is highlighted.

Indicator “node” points to “e”.

Printed: b d a g e

Card 10: Return to c; print c.

The call for e has returned to c, completing c's left subtree. Print c now, between its left and right subtrees.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: b d a g e c

Card 11: Descend to f.

Move from c to its right child, f. The call for f waits while its left subtree is traversed. Its value will be printed after that subtree returns.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: b d a g e c

Card 12: Descend to h; print h.

Move from f to its left child, h. h has no left child, so its left-subtree call returns immediately. Print h before traversing its right subtree.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“h” is highlighted.

Indicator “node” points to “h”.

Printed: b d a g e c h

Card 13: Return to f; print f.

The call for h has returned to f, completing f's left subtree. Print f now, between its left and right subtrees.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: b d a g e c h f

Card 14: Descend to i; print i.

Move from f to its right child, i. i has no left child, so its left-subtree call returns immediately. Print i before traversing its right subtree.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“i” is highlighted.

Indicator “node” points to “i”.

Printed: b d a g e c h f i

Card 15: Return from i to f.

The call for i has returned to f, completing f's right subtree. f was printed before its right subtree; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: b d a g e c h f i

Card 16: Return from f to c.

The call for f has returned to c, completing c's right subtree. c was printed before its right subtree; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: b d a g e c h f i

Card 17: Return from c to a.

The call for c has returned to a, completing a's right subtree. a was printed before its right subtree; returning to it leaves the printed sequence unchanged.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: b d a g e c h f i

Card 18: Inorder traversal is complete.

The call for the root has returned. Every node has been printed once. The node indicator has no current target.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

Indicator “node” has no target.

Printed: b d a g e c h f i

Run It

#include <iostream>

template <class T>
void print(tree<T>* node) {
  if (node == nullptr) {
    return;
  }
  print(node->left);
  std::cout << node->value << ' ';
  print(node->right);
}

int main() {
  std::cout << "Inorder: ";
  print(make_tree());

  return 0;
}

6.4.1.4. Level order traversal

Differs from the previous traversals: it is a 'breadth first' traversal. Also, this algorithm is easier to implement iteratively than recursively.

Visit each node on each level of the tree then visit the children one level deeper.

Level order

This is an iterative, not a recursive function.

void levelorder(tree<T>* node) {
  if (node == nullptr) {
    return;
  }
  std::queue<tree<T>*> q;
  q.push(node);
  while (!q.empty()) {
    auto tmp = q.front();
    visit(tmp);
    q.pop();
    if(tmp->left)  q.push(tmp->left);
    if(tmp->right) q.push(tmp->right);
  }
}

Level order traversal: print each level from left to right

Card 1: Start with the root in the queue.

Put a in the queue. The node indicator points to the next value to process. The queue is shown with its front on the left; no value has been printed yet.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: (none)

Queue (front first): a

Card 2: Print a; process its children.

The node indicator marks a, the front item. Print a, remove it from the queue, then process its children. Enqueue b and c at the back, with the left child before the right child.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“a” is highlighted.

Indicator “node” points to “a”.

Printed: a

Queue (front first): b c

Card 3: Print b; process its children.

The node indicator marks b, the front item. Print b, remove it from the queue, then process its children. Enqueue d at the back.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“b” is highlighted.

Indicator “node” points to “b”.

Printed: a b

Queue (front first): c d

Card 4: Print c; process its children.

The node indicator marks c, the front item. Print c, remove it from the queue, then process its children. Enqueue e and f at the back, with the left child before the right child.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“c” is highlighted.

Indicator “node” points to “c”.

Printed: a b c

Queue (front first): d e f

Card 5: Print d; process its children.

The node indicator marks d, the front item. Print d, remove it from the queue, then process its children. This node has no children to enqueue.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“d” is highlighted.

Indicator “node” points to “d”.

Printed: a b c d

Queue (front first): e f

Card 6: Print e; process its children.

The node indicator marks e, the front item. Print e, remove it from the queue, then process its children. Enqueue g at the back.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“e” is highlighted.

Indicator “node” points to “e”.

Printed: a b c d e

Queue (front first): f g

Card 7: Print f; process its children.

The node indicator marks f, the front item. Print f, remove it from the queue, then process its children. Enqueue h and i at the back, with the left child before the right child.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“f” is highlighted.

Indicator “node” points to “f”.

Printed: a b c d e f

Queue (front first): g h i

Card 8: Print g; process its children.

The node indicator marks g, the front item. Print g, remove it from the queue, then process its children. This node has no children to enqueue.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“g” is highlighted.

Indicator “node” points to “g”.

Printed: a b c d e f g

Queue (front first): h i

Card 9: Print h; process its children.

The node indicator marks h, the front item. Print h, remove it from the queue, then process its children. This node has no children to enqueue.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“h” is highlighted.

Indicator “node” points to “h”.

Printed: a b c d e f g h

Queue (front first): i

Card 10: Print i; process its children.

The node indicator marks i, the front item. Print i, remove it from the queue, then process its children. This node has no children to enqueue.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

“i” is highlighted.

Indicator “node” points to “i”.

Printed: a b c d e f g h i

Queue (front first): (empty)

Card 11: Level order traversal is complete.

The queue is empty. Every node has been printed once, one level at a time from left to right. The node indicator has no current target.

Text description

Tree diagram with 9 visible nodes.

The root is “a”.

“a” has left child “b” and right child “c”. “b” has right child “d”. “c” has left child “e” and right child “f”. “e” has left child “g”. “f” has left child “h” and right child “i”.

“d”, “g”, “h”, and “i” are leaves.

Indicator “node” has no target.

Printed: a b c d e f g h i

Queue (front first): (empty)

Run It

#include <iostream>
#include <queue>

template <class T>
void print(tree<T>* node) {
  if (!node) return;

  std::queue<tree<T>*> q;
  q.push(node);
  while (!q.empty()) {
    auto tmp = q.front();
    std::cout << tmp->value << ' ';
    q.pop();
    if(tmp->left)  q.push(tmp->left);
    if(tmp->right) q.push(tmp->right);
  }
}

int main() {
  std::cout << "Level order: ";
  print(make_tree());

  return 0;
}

---

More to Explore

• Containers library

• Visualgo: binary heap