15.2. Binary Search Trees

A binary tree T is a binary search tree if, for each node n with sub-trees left and right,

  • The value in n is greater than the values in every node in left.

  • The value in n is less than the values in every node in right.

  • Both left and right are binary search trees.

This page uses unique keys, like std::set. If a value equivalent to an existing value is inserted, the insertion has no effect. Two values are equivalent when neither compares less than the other. The comparisons are assumed to define a strict weak ordering, as they do for the keys in an ordered standard-library container. A production tree would usually make that ordering an explicit comparator type.

These assertions define the binary search tree property.

a binary search tree

Is this a BST?

Yes.

Each node is greater than all of its left descendants, and is less than all of its right descendants. Equivalent values are not inserted.

15.2.1. The Binary Search Tree ADT

Structurally, a BST contains pointers to its left and right children. As discussed in Recursion, a binary tree can be implemented simply as a recursive data structure. A binary search tree can also be implemented recursively.

It is a bit simpler to define the tree nodes as a separate type. Whether you design this class as a completely independent class, like this one, or implement it as a nested (inner) class, is largely a matter of choice.

Since a tree_node is a data structure that can exist independently of a tree that enforces the binary search tree property, it makes sense in this case to define it as a completely separate struct with no invariants.

The tree_node encapsulates the general characteristics common to all binary trees:

  • A variable to store the node value

  • Links to the left and right child nodes, which might themselves be sub-trees.

BST node

The node stores a value and owns its children. A null unique_ptr means that the corresponding child is absent. The node itself does not enforce the binary search tree property; the tree operations do that.

#include <memory>

template<class T>
struct tree_node {
  T value;
  std::unique_ptr<tree_node> left;
  std::unique_ptr<tree_node> right;

  explicit tree_node(const T& value) : value{value} {}
};

Print

An in-order traversal function allows us to print values in ascending order for a binary search tree.

#include <iostream>

template<class T>
void print_in_order(const tree_node<T>* node) {
  if (node == nullptr) {
    return;
  }
  print_in_order(node->left.get());
  std::cout << node->value << ' ';
  print_in_order(node->right.get());
}

Run It

 1#include <memory>
 2
 3template<class T>
 4struct tree_node {
 5  T value;
 6  std::unique_ptr<tree_node> left;
 7  std::unique_ptr<tree_node> right;
 8
 9  explicit tree_node(const T& value) : value{value} {}
10};
11
12#include <iostream>
13
14template<class T>
15void print_in_order(const tree_node<T>* node) {
16  if (node == nullptr) {
17    return;
18  }
19  print_in_order(node->left.get());
20  std::cout << node->value << ' ';
21  print_in_order(node->right.get());
22}
23
24int main() {
25  auto root = std::make_unique<tree_node<int>>(4);
26  root->left = std::make_unique<tree_node<int>>(2);
27  root->right = std::make_unique<tree_node<int>>(6);
28  root->left->left = std::make_unique<tree_node<int>>(1);
29  root->left->right = std::make_unique<tree_node<int>>(3);
30  root->right->left = std::make_unique<tree_node<int>>(5);
31  root->right->right = std::make_unique<tree_node<int>>(7);
32
33  print_in_order(root.get());
34  std::cout << '\n';
35}

In other words, a tree_node is a general purpose binary tree data structure and has no knowledge of any binary search tree properties or behavior.

Much like our earlier tree objects, all of the functions used to manipulate a tree_node will be free functions. To avoid collision with other similarly named functions, all the functions will be defined in the mesa::tree namespace.

The binary search tree is built up from individual tree_node objects. An owning bstree should store its root in a std::unique_ptr so that destroying the root recursively destroys its children. This makes ownership explicit and prevents the leaks that are easy to introduce with raw owning pointers.

The default copy operations of a class containing std::unique_ptr are deleted. A class with std::set-like copyable behavior would need to write a deep-copy operation; that ownership detail is separate from the search-tree algorithms. The complete examples below use move-only ownership and return non-owning node pointers as temporary position handles. The next page replaces those handles with proper tree iterators.

Our primary focus for the rest of this section is on the functions that define the key operations associated with a BST:

  • contains and find

  • insert and erase

15.2.2. Searching binary trees

Efficient search of a binary tree uses the same algorithm you would use when playing the 'number guessing' game. If asked to guess a random number between 1 and 100 in the fewest possible tries, with a hint higher or lower after each attempt, few people would start at 1, then guess 2, 3, and so on until they guessed correctly. Most people would start with 50 and continue to split the remaining unknown partition in half until they found the correct number.

The strategy most people apply to this problem intuitively is known as the binary search algorithm. This algorithm is easily applied to binary search trees.

The running time of a search is \(O(h)\), where h is the height of the tree. A balanced BST has height \(O(\log N)\), while a tree built from already sorted input can have height \(O(N)\) -- in other words, a list.

contains

We always search a binary search tree by comparing the value we're searching for to the 'current' node value. If the target value is smaller, then we search the left subtree. If the target value is larger, then we search the right subtree.

If it is neither of these things, then we found the value.

 1#include <iostream>
 2
 3template<class T>
 4bool contains(const tree_node<T>* node, const T& query_value) {
 5  if (node == nullptr) {
 6    return false;
 7  }
 8  if (query_value < node->value) {
 9    return contains(node->left.get(), query_value);
10  }
11  if (node->value < query_value) {
12    return contains(node->right.get(), query_value);
13  }
14  return true;
15}
16
17int main() {
18  auto root = std::make_unique<tree_node<int>>(4);
19  root->left = std::make_unique<tree_node<int>>(2);
20  root->right = std::make_unique<tree_node<int>>(6);
21  root->left->left = std::make_unique<tree_node<int>>(1);
22  root->left->right = std::make_unique<tree_node<int>>(3);
23
24  std::cout << std::boolalpha
25            << contains(root.get(), 3) << ' '
26            << contains(root.get(), 5) << '\n';
27}

15.2.3. Inserting into binary trees

Inserting into a binary tree means adding a new node in the tree such that the binary search tree property remains intact.

Insertion also takes \(O(h)\) time, where h is the tree height. A balanced BST therefore supports insertion in \(O(\log N)\) time, while an unbalanced tree can require \(O(N)\) time.

insert

The insert process begins with a search for a place to insert a new value. But how do we find the place at which to insert that new node? Ask "where would we go if we were searching for this data in the tree?" This process is identical to the search used for the contains function.

The standard std::set::insert contract returns a pair containing a position and a Boolean. The Boolean is true only when insertion took place; inserting an equivalent value has no effect. This example uses a non-owning node pointer as the position until the next page introduces a real tree iterator.

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

There are a few important things to notice about this function.

The insert function receives the current owning pointer by reference. It can replace that pointer when traversal reaches an empty child link. A new node is inserted at that null link, below a leaf or in place of an empty child of an internal node.

When the value is equivalent to an existing value, the function returns the existing node and false. It does not overwrite the value, which is an implementation choice. Another container implementation might have chosen to overwrite, but in this case, we are matching the standard library behavior.

Run It

 1template<class T>
 2std::pair<tree_node<T>*, bool>
 3insert(std::unique_ptr<tree_node<T>>& node, const T& value) {
 4  if (node == nullptr) {
 5    node = std::make_unique<tree_node<T>>(value);
 6    return {node.get(), true};
 7  }
 8  if (value < node->value) {
 9    return insert(node->left, value);
10  }
11  if (node->value < value) {
12    return insert(node->right, value);
13  }
14  return {node.get(), false};
15}
16
17int main() {
18  std::unique_ptr<tree_node<int>> root;
19  insert(root, 4);
20  insert(root, 2);
21  insert(root, 6);
22  auto result = insert(root, 4);
23
24  std::cout << std::boolalpha
25            << "inserted duplicate: " << result.second << '\n';
26  print_in_order(root.get());
27  std::cout << '\n';
28}

Try This!

Walk through this algorithm yourself with different sets of values.

Experiment with inserting nodes into binary search trees. Take particular note of what happens if you insert data in ascending or descending order, as opposed to inserting unordered data.

15.2.4. Erasing binary tree nodes

The erase process also begins with a search for the place to erase. This process is identical to the search used for contains and insert.

The tricky part of removing a value from a binary search tree is what to do when we actually find the value we want to delete. We can't just delete the tree node. Consider the following tree.

a binary search tree

If we remove values 10, 40, or 60 by simply deleting the tree node, that might work. However, deleting any other node would break the links between tree nodes.

We have three cases to consider:

  • Removing a leaf

  • Removing a node that has only one child

    • only a left child

    • only a right child

  • Removing a node that has two children

15.2.4.1. Removing a leaf node

It's easy to see that we can always remove any leaf in a binary search tree without affecting anything else. That is, if we remove any leaf from a binary search tree, we still have a valid binary search tree. There is nothing else to do.

When node points to a leaf that contains the data we want to remove we replace the owning pointer in node with an empty pointer. With std::unique_ptr, assigning nullptr automatically destroys the removed node.

In other words, leaf nodes are replaced with the null pointer.

15.2.4.2. Removing a non-leaf node with a null child

Removing nodes from the interior of the tree is a bit more work as we need to maintain links between nodes.

Given the same tree we have been working with so far:

a binary search tree

Question Suppose we wanted to remove the 20 or the 70 from this tree. What would we have to do so that the remaining nodes would still be a valid BST?

Show

There is one pointer to the node being deleted, and one pointer from that node to its only child.

So this is actually a bit like deleting a node from the middle of a linked list.

All we need to do is to update the pointer from the parent 30 node. That pointer should point to the child of the node we are going to remove.

a binary search tree

Verify that if we remove either 20 or 70, the resulting tree is still a valid binary search tree.

a binary search tree with 20 removed

a binary search tree

The code we used to remove a leaf also works when there is only one child.

If we reach this code, we know there is at most one non-null child. In the previous case of a leaf node, both children are null, but the same ownership replacement works for one child also.

If the left child is not null, then reassign the left child to the current node, otherwise assign the right child.

15.2.4.3. Removing a non-leaf node with two children

Suppose we wanted to remove the 50 or the 30 from this tree. What must we do so that the remaining nodes would still be a valid BST?

This is a hard case. If we remove either the 50 or 30 nodes, then we break the tree into pieces, with no obvious place to put the now-detached subtrees.

a binary search tree

There is an efficient solution to this problem. Instead of deleting the node when we find it, is there some other data value that we could put into that node that would preserve the BST property?

There are, in fact, two values that we could safely put in there:

  • the smallest value from the right subtree

  • the largest value from the left subtree

We can find the largest value on the left by

  • taking one step to the left

  • then running as far down to the right as we can go

We can find the smallest value on the right by

  • taking one step to the right

  • then running as far down to the left as we can go

a binary search tree

a binary search tree

At this point, we haven't deleted or created any nodes. We simply copy a value from one node to another. Now we have two nodes in our tree with the same value, either 20 or 40, depending on which approach we used.

We still need to delete the smallest right node or the largest left node. What makes this last step simple is that it falls under our previous case: it is by definition either a leaf, or has at most one child.

a binary search tree

a binary search tree

erase

Putting it all together.

Recall that std::unique_ptr is not copyable or copy constructible. Moving a unique_ptr is allowed.

 1template<class T>
 2void erase(std::unique_ptr<tree_node<T>>& node, const T& value) {
 3  if (node == nullptr) {
 4    return;
 5  }
 6  if (value < node->value) {
 7    erase(node->left, value);
 8    return;
 9  }
10  if (node->value < value) {
11    erase(node->right, value);
12    return;
13  }
14
15  if (node->left == nullptr) {
16    node = std::move(node->right);
17    return;
18  }
19  if (node->right == nullptr) {
20    node = std::move(node->left);
21    return;
22  }
23
24  const tree_node<T>* successor = node->right.get();
25  while (successor->left != nullptr) {
26    successor = successor->left.get();
27  }
28  node->value = successor->value;
29  erase(node->right, successor->value);
30}
31
32int main() {
33  std::unique_ptr<tree_node<int>> root;
34  for (int value : {50, 30, 70, 20, 40, 60, 80}) {
35    insert(root, value);
36  }
37
38  erase(root, 20);  // leaf
39  erase(root, 60);  // leaf
40  erase(root, 70);  // one child: 80 remains
41  erase(root, 50);  // two children
42  print_in_order(root.get());
43  std::cout << '\n';
44}

Lines 6-13 handle the search we discussed initially. Here we recursively search for our target value to remove.

The last if block handles the case with 2 children. We find the smallest node in the right subtree and assign its value to the current node. Then we erase this value from the right subtree of the current node.

The final block handles the leaf and the one child cases. This is the only case where a node is actually removed from the tree. This block will also ultimately get called when the case handling two child nodes needs to delete the smallest value from the right subtree.

More to Explore