15.3. Binary Search Tree iterators

The recursive traversal algorithms work well for implementing tree-based ADT member functions. If we hide the tree inside an ADT, however, we need an iterator so users can apply standard-library algorithms and range-for loops. For example, a binary search tree can provide the ordered interface of std::set.

Iterators for tree-based data structures can be more complicated than those for linear structures.

For arrays (and vectors and deques and other array-like structures) and linked lists, a single pointer can implement an iterator.

Given the current position, it is easy to move forward to the next element.

For anything but a singly-linked list, we can also easily move backwards.

But look at this binary search tree, and suppose that you were implementing tree iterators as a single pointer. Let's see if we can "think" our way through the process of traversing this tree one step at a time, without needing to keep a whole stack of unfinished recursive calls around.

We're going to try to visit the nodes in the same order we would process them during an "in-order" traversal. For a BST, in-order traversal means that we will visit the data in ascending order.

It's not immediately obvious what our data structure for storing the "current position" (i.e., an iterator) will be. We might suspect that a pointer to a tree node will be part of that data structure, because that worked with iterators over linked lists.

15.3.1. BST iterator begin() and end()

As in any data structure, begin and end refer to the first element in the data structure and one past the last element. The previous page showed that a BST produces sorted values when visited using an in-order traversal.

So what algorithm should we use to find the beginning?

Show

Start from the root and work our way down, always taking left children, until we come to a node with no left child.

The left-most child of a BST is always the minimum element.

So what algorithm should we use to find the end?

Show

Just return the nullptr.

It's tempting to guess that you could do much the same as for begin(), this time seeking out the right-most node. But that would leave you pointing to the last node in the tree, and end() must always refer to the position after the last element in the container.

15.3.2. BST iterator operator++()

A quick review of the definition of iterators and the iterator design pattern. We have a few facts to deal with:

• A tree is a hierarchical data structure

• An iterator allows users to visit each element in a container sequentially - with no awareness of the underlying structure.

• In C++, iterators are implemented using pointer semantics. The function operator++() is used to move to the next element.

Given our familiar tree:

If we are iterating through our tree and are currently at the node with value 40, then how do we get to the next node?

Show

Well, we know that we should wind up at 50. But how can we get there?

We can't, not with just a pointer to the node and all the nodes pointing only to their children.

The only place you can go within this tree is down, and there is no "down" from our current position.

In a binary tree, to get to the next node, we need to know not only where we are, but also how we got here.

One way is to do that is to implement the iterator as a stack of pointers containing the path to the current node. The stack would be used to simulate the activation stack during a recursive traversal.

But this solution is clumsy and inefficient. Iterators tend to get assigned (copied) a lot, and we'd really like that to be a constant time - an \(O(1)\) operation. Having to copy an entire stack of pointers just isn't very attractive.

15.3.2.1. BST iterator using parent pointers

We can make the task of creating tree iterators much easier if we redesign the tree nodes to add a pointer from each node to its parent. The child pointers remain owning std::unique_ptr objects. The parent pointer is a non-owning observer; it must never be used to delete a node.

#include <memory>

template<class T>
struct tree_node {
  T value;
  std::unique_ptr<tree_node> left;
  std::unique_ptr<tree_node> right;
  tree_node* parent = nullptr;

  explicit tree_node(const T& node_value, tree_node* parent_node = nullptr)
    : value{node_value}, parent{parent_node} {}
};

The tree class owns the root. Every child is owned by its parent, while each parent pointer only points back toward an object that is owned elsewhere. This ownership direction prevents cycles and lets destroying the root destroy the complete tree.

The outline for a tree iterator is similar to what we have covered before:

#include <cstddef>
#include <iterator>

template<class T>
struct tree_iterator {
  using value_type = T;
  using pointer = const T*;
  using reference = const T&;
  using difference_type = std::ptrdiff_t;
  using iterator_category = std::bidirectional_iterator_tag;

  const tree_node<T>* node = nullptr;

  tree_iterator() = default;
  explicit tree_iterator(const tree_node<T>* node) : node{node} {}

  reference operator*() const noexcept { return node->value; }
  pointer operator->() const noexcept { return &node->value; }
  bool operator==(const tree_iterator& other) const noexcept {
    return node == other.node;
  }
  bool operator!=(const tree_iterator& other) const noexcept {
    return !(*this == other);
  }
  tree_iterator& operator++();
  tree_iterator operator++(int);
  tree_iterator& operator--();
  tree_iterator operator--(int);
};

There is a subtlety when using our tree iterator in a BST. This page provides read-only iterators: the iterator object can be copied and incremented, but its reference type is const T&. Dereferencing an iterator therefore allows us to view a value without modifying it.

template<class T>
class bstree {
public:
  using value_type = T;
  using iterator = tree_iterator<T>;
  using const_iterator = iterator;
  using reference = typename iterator::reference;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = reverse_iterator;

  // remainder omitted . . .
};

The iterator type itself is not const. It must be assignable and incrementable. Instead, bstree::reference is const T&, so users cannot reassign data in the tree:

bstree<int>::iterator it = myTree.find(50);
*it = 10000;  // error: *it is a const int&

which would very likely break the internal ordering of data, violating the binary search tree property, and making it useless for any future searches. A read-only iterator allows us to look at data in the container, but not change that data.

The reverse iterator is the standard std::reverse_iterator wrapper around our tree_iterator. It moves backward by calling the underlying iterator's decrement operators. Implementing tree_iterator::operator-- and its postfix form is intentionally left as a homework assignment; the reverse traversal algorithm is not provided on this page.

15.3.3. Implementing BST iterators

As discussed earlier, begin() is implemented by finding the minimum element in the tree.

A free function that works with the tree_node struct is enough:

template <class T>
const tree_node<T>* min_element(const tree_node<T>* root) {
  if (root == nullptr || root->left == nullptr) {
    return root;
  }
  return min_element(root->left.get());
}

bstree::begin() can use this function directly:

const_iterator begin() const noexcept {
  return const_iterator(min_element(root.get()));
}

And end() uses the null pointer.

const_iterator end() const noexcept {
  return const_iterator(nullptr);
}

15.3.3.1. Implementing operator++()

Before implementing operator++, let's think about what it should do. Given the following tree:

(Not a binary search tree, just a tree).

Question: Suppose that we are currently at node E. What is the in-order successor of E? That is, the node that comes next during an in-order traversal of E?

Show

G is the in-order successor of E.

If you answered F, remember that in an in-order traversal, we visit a node only after visiting all of its left descendants and before visiting any of its right descendants. Since we're at E, we must have already visited F.

That example suggests that a node's in-order successor tends to be among its right descendants.

If our previous premise is correct, then what is the in-order successor to A?

Show

F is the in-order successor of A.

If we are at A during an in-order traversal, then we have already visited all of A's left descendants. So the answer has to be C or one of its descendants. It's tempting to pick C because it's only one step away from A.

But, remember, during an in-order traversal, we visit a node only after visiting all of its left descendants and before visiting any of its right descendants.

We have not yet visited C's left descendants. So have to run down from C to the left as far as we can go.

This suggests that, if a node has any right descendants, we should:

• Take a step down to the right, then

• Run as far down to the left as we can.

You can see how this would take us from A to F. The same approach would take us from E to G as well. So both of our prior examples are satisfied.

But that "step to the right, then run left" procedure raises a new question. What happens if we are at a node with no right descendants?

Question: Suppose that we are currently at node C. What is the in-order successor of C?

Show

C does not have an in-order successor. C is actually the final node in an in-order traversal. After C is only end().

While node C is an interesting special case, it doesn't make clear what should happen in the more general case where we have no right child.

Question: What is the in-order successor of F?

Show

E is the in-order successor of F.

So, when we have no right child, we may need to move back up in the tree.

Question: What is the in-order successor of G?

Show

C is the in-order successor of G.

Why did we move up two steps in the tree this time, when from F we only moved up one step? The answer lies in whether we moved back up over a left-child edge or a right-child edge.

If we move up over a right-child edge, we're returning to a node that has already had all of its descendants, left and right, visited. So we must have already visited this node as well, otherwise we would never have made it into its right descendants.

If we move up over a left-child edge, then we're returning to a node that has already had all of its left descendants visited but none of its right descendants. That's the definition of when we want to visit a node during an in-order traversal, so it's time to visit this node.

So, if a node has no right child, we move up in the tree (following the parent pointers) until we move back over a left edge. Then we stop.

When applying this procedure to C, we move up to A (right edge), then try to move up again to A's parent. But since A is the tree root, its parent pointer will be null, which is our signal that C has no in-order successor.

To summarize:

• If the current node has a non-null right child,

  • Take a step down to the right

  • Then run down to the left as far as possible

• If the current node has a null right child,

  • Move up the tree until we have moved over a left child link

operator++

Putting it all together.

template<class T>
tree_iterator<T>& tree_iterator<T>::operator++() {
  if (node == nullptr) {
    return *this;
  }
  if (node->right != nullptr) {
    // Find the smallest node in the right subtree.
    node = min_element(node->right.get());
  } else {
     // Search upward for the first parent reached over a left edge,
     // or nullptr when this node is the final value.
     auto parent = node->parent;
     while (parent != nullptr && node == parent->right.get()) {
       node = parent;
       parent = parent->parent;
     }
     node = parent;
  }
  return *this;
}

One part of this iterator that needs closer inspection is the while loop. This loop continues moving upwards in the tree until it finds:

• A node where the current node is the left child of its parent, or

• The root of the tree (parent == nullptr), indicating that there is no in-order successor (end of the traversal).

Key Conditions

• parent != nullptr: Ensures we do not dereference a nullptr when accessing parent->right.

• node == parent->right.get(): Asserts the current node is the right child of its parent. When true, we need to keep moving upwards, as the in-order successor is not in this part of the tree.

The loop climbs up the tree until it finds a node for which the current traversal has completed its right subtree. This ensures that the in-order successor is correctly identified.

Consider an alternative approach that simply checks the immediate parent:

if (parent != nullptr && node == parent->right.get()) {
    node = parent;
    parent = parent->parent;
}

The issue with this approach is that it would only handle one level of traversal upwards. If the current node is deeply nested in a right subtree, it may skip multiple ancestors that need to be visited to find the in-order successor. This can cause incorrect results when:

• The node is the rightmost descendant of a deep subtree, requiring multiple upward traversals to reach the root or an ancestor in a left subtree.

• Randomly generated trees or trees that have had many insertions and removals from the tree may have imbalanced structures with chains of right children, requiring multiple iterations of the while loop.

Consider this tree:

If the iterator is at 20 (the rightmost node):

• The while loop will correctly climb from 20 --> 15 --> 10, and stop when parent == nullptr.

• A single conditional would move only one step (to 15) and fail to reach the root, leaving the iterator in an inconsistent state.

The following example combines the node, insertion, iterator, and successor fragments to walk the tree in ascending order.

#include <iostream>

int main() {
  std::unique_ptr<tree_node<int>> root;
  for (int value : {30, 20, 70, 50, 40, 60}) {
    insert(root, value);
  }

  tree_iterator<int> begin{min_element(root.get())};
  tree_iterator<int> end;
  while (begin != end) {
    std::cout << *begin << ' ';
    ++begin;
  }
  std::cout << '\n';
}

15.3.4. Using parent pointers

Using parent pointers does incur additional overhead: every tree node stores one more non-owning pointer. It also means insertion must maintain the parent relationship whenever it creates a child.

The insertion contract remains the same as the previous page and as std::set::insert: equivalent values are not inserted, and the returned Boolean reports whether a new node was created. The returned node pointer is a non-owning position handle; a later section replaces that handle with an iterator.

#include <memory>
#include <utility>

template<class T>
std::pair<tree_node<T>*, bool>
insert(std::unique_ptr<tree_node<T>>& node,
       const T& value,
       tree_node<T>* parent = nullptr) {
  if (node == nullptr) {
    node = std::make_unique<tree_node<T>>(value, parent);
    return {node.get(), true};
  }
  if (value < node->value) {
    return insert(node->left, value, node.get());
  }
  if (node->value < value) {
    return insert(node->right, value, node.get());
  }
  return {node.get(), false};
}

When a new node is made, the current node is passed to the constructor as its parent. The recursive call also passes the current node when it descends into either child. Notice that the child remains owned by its unique_ptr; parent is only an observer.

The following small program builds a parent-aware tree and verifies both the unique-key insertion result and one parent link.

#include <iostream>

int main() {
  std::unique_ptr<tree_node<int>> root;
  for (int value : {30, 20, 70, 50, 60}) {
    insert(root, value);
  }
  auto duplicate = insert(root, 50);

  std::cout << std::boolalpha
            << "inserted duplicate: " << duplicate.second << '\n'
            << "parent of 50: " << root->right->left->parent->value
            << '\n';
}

---

More to Explore

• The content on this page was adapted from Binary Search Trees, by Steven J. Zeil for his data structures course CS361.

• Binary tree visualizer