Chapter 8 Binary Search Trees

8.1 Trees

Up to this point we have dealt with linear data structures. In some sense, the items were always stored one after the other. There was always some kind of linear arrangement to the way that the data was stored and there was the concept of the next item in the structure. From here onwards, we will focus on data structures that are non-linear. We will consider various types of trees and the algorithms associated with them.

Trees allow us to model hierarchical relationships between data where there is a parent and a child. For example, a filesystem has directories that can contain other subdirectories and files. A directory is the parent of all the items inside it and the items inside the directory are the children.

Another reason to use a tree is when we have large amounts of data and the access and search times associated with lists become too expensive. By organising data in a tree, we can achieve search times of \(O(logn)\) in comparison to \(O(n)\) that we would usually get when searching through a vector or linked list. This change might not seem substantial, but note that a running time of \(O(logn)\) is exponentially faster than \(O(n)\).²⁶ If there are 1 million items in a vector, then a linear search would perform 1 million comparisons in the worst case. With a balanced binary tree, we could search the entire list for a number under 20 comparisons. In fact, this is how database systems work – they build an index using some kind of balanced binary tree (usually a B-Tree) which allows for exceptionally fast lookups even when there is a very large amount of data to search through.

We represent a tree as a set of vertices and edges. Each vertex represents a value that is stored in the tree and each edge represents the connection between a parent and a child. Every vertex has exactly 1 parent, except for the root which does not have a parent.

“A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of a distinguished node, r, called the root, and zero or more nonempty (sub)trees \(T_1, T_2, \ldots, T_k\) each of whose roots are connected by a directed edge from r.”

Weiss (2014)

A tree then has \(n-1\) edges. A path from node \(n_j\) to \(n_k\) is a sequence of nodes such that there is an edge between any two consecutive nodes in the sequence. The length of the path is the number of edges that would be traversed moving from \(n_j\) to \(n_k\).

A node can have any number of children. Nodes that share the same parent are called siblings. A node is called an internal node if it has one or more children. A node that has no children is called a leaf. The depth of a node is the length of the path from the root to that node. The height of the tree is the length of the longest path from the root to any leaf.

If we speak of a subtree that is rooted at \(n_k\), this means we are speaking of the node \(n_k\) and all of the edges and vertices that are descendants of that node.

8.2 Binary Trees

A tree where every node has a maximum of two children is called a Binary Tree and in this case, we can speak of the left and right subtrees. We can speak of the level of a node, the root has level \(0\), its children are on level \(1\) etc. A child’s level is the parent’s level \(+1\). A binary tree of height \(h\) will have \(h+1\) levels. A binary tree with \(2^k\) nodes in level \(k\) is called a perfect binary tree. A binary tree where each node has zero or two children is called full or proper. A tree of height \(h\) that is perfect up to level \(h-1\) and then fills up from the left in level \(h\) is called a complete binary tree.

Let \(n\) denote the number of nodes, \(n_l\) denote the number of leaves, \(n_i\) denote the number of internal nodes and \(h\) is the height of the tree. Then the following relationships hold:

\(log_2(n+1) -1 \leq h \leq n-1\)
\(h + 1 \leq n \leq 2^{h+1}-1\)
\(n_l = n_i + 1\)
\(n = 2n_i + 1\)
\(n_i = (n-1)/2\)
\(n_l = (n+1)/2\)
\(n = 2n_l -1\)
\(n_i = n_l - 1\)

The first relationship is significant and gives us bounds on several algorithms that run from the root down a path until it reaches a leaf.

8.3 Binary Search Tree

An ordered binary tree is known as a Binary Search Tree (BST). A BST is a binary tree with the added constraint that all values stored in the left subtree of node \(n_k\) must be less than the value stored in \(n_k\) and all the values stored in the right subtree must be greater than or equal to the value stored in \(n_k\). The order property must hold for every node in the entire tree.

8.3.1 Insertion

Inserting a value into a BST requires that we start at the root and compare the value to be inserted with the value at the current node. If the value to be inserted is less than the current node’s value, then we should recursively insert the value into the left subtree, otherwise, we should recursively insert the value into the right subtree. When we find an empty space in the tree (e.g. we need to insert into the left subtree and there is no left child) then we create a node with the new value and insert that node into the space.

In the worst case, our algorithm needs to traverse the tree along the longest path from the root to a leaf before inserting. In this case, we traverse \(h\) nodes before we can perform the insert. So in the worst case, the amount of work done is proportional to the height of the tree.

From the relationships in Section 8.2 above, this means that the amount of work we need to do will depend on the structure of the tree. In the best case, the height of the tree will be \(log_2(n+1)-1\) and in the worst case, the height of the tree will be \(n-1\). In Big-O notation, we are interested in the shape of these functions and so we say that the height is \(O(logn)\) or \(O(n)\) respectively.

When the height of the tree is \(O(n)\) we say that the tree is degenerate, and it has basically become a linked list. In later chapters we will consider algorithms that help make sure that the tree is always balanced and therefore has a height that is \(O(logn)\).

8.3.2 Searching

If we would like to search for a value, \(x\), we follow a similar approach. Again we start at the root and compare \(x\) with the value of the current node. If it is equal then we have found the value, if \(x\) is less than the current node’s value, then we should recursively search the left subtree, otherwise, we should recursively search the right subtree. If the subtree being searched is ever empty, then it means that \(x\) is not present in the BST.

In the worst case, the number is not in the tree and the path we follow corresponds to the longest path from the root to a leaf. In this case, we traverse \(h\) times, so the amount of work done is proportional to the height of the tree. Just as in the case of insertion, this means that we will do either \(O(logn)\) or \(O(n)\) depending on the structure of the tree. In the best case, the search key (\(x\)) is the value stored in the root and we do \(O(1)\) amount of work.

8.3.3 Min & Max

The minimum or maximum values in a BST can be found by repeatedly traversing to the left or right.

To find the minimum value, we start at the root and repeatedly traverse left (curr = curr->left) until we encounter a node that does not have a left child. This is then the minimum value in the tree. Similarly, by repeatedly traversing to the right, we will find the maximum value.

8.3.4 Delete

To remove a value from the tree we need to consider what happens to that node’s children. There are three different cases to consider.

When the node has no children, then we can simply delete the node, and set the parent’s child pointer to nullptr. This process resembles deleting the last link in a linked list.

When the node has one child, then we need to set the parent’s child pointer to point to the current node’s child. After that is done then we can delete the current node.

Finally, when the node has two children, then we need to replace the value inside the current node with the successor. This means we need to find the next largest value in the tree and move it to the current node. We can then delete that value from the relevant subtree. The next largest value in the BST will be the minimum value in the right subtree. So we traverse to the right subtree and then traverse as far left as possible. This value can simply replace the value that was being deleted, and then we recursively delete that new value from the right subtree. We are guaranteed that in that case, then it will have zero or one child and the deletion can take place using the strategies above.

Using the proof techniques from DCS, how do you think you could prove that the successor does not have a left child?

8.4 Tree Traversals

8.4.1 Depth First Traversals

Sometimes we would like to traverse over the entire tree, visiting each node in a specified order. We can do this by performing a Depth First Search. At each step, we can process/print the current value, process all the values in the left subtree, and process all the values in the right subtree. The order in which we do this creates three different traversals:

Pre-Order Traversal
- Value, Left, Right
In-Order Traversal
- Left, Value, Right
Post-Order Traversal
- Left, Right, Value

Each of these traversals achieves a different task. The in-order traversal will give us all of the values in order. This means that we could sort a list by constructing a BST and then performing an in-order traversal. The pre-order traversal can be used to serialise the tree. If we perform a pre-order traversal, we will get a list of numbers that, if used with the standard insertion algorithm, will recreate the tree. If we perform a post-order traversal, then we can use the tree to construct postfix expressions as seen in Section 6.5.1.

All of these traversals have elegant recursive implementations:

void BST::in_order_traversal(Node* curr){
  if(curr == nullptr) return;
  
  in_order_traversal(curr->left);
  cout << curr->value << " ";
  in_order_traversal(curr->right);
}

8.4.2 Breadth-First or Level Traversals

We could perform a breadth-first search where we visit the nodes in the tree level by level. We first consider the root (at level 0), then we consider all nodes at level 1, then all nodes at level 2 and continue in this way until we have visited all nodes.

8.5 Lab: Binary Search Trees

For this lab, you need to implement your own Binary Search Tree. This lab is graded using unit tests rather than IO marking – you submit a single implementation file, and the tests call the methods of your Tree class directly, so you don’t need to worry about reading input or formatting output at all.

8.5.1 The Header

You must implement your Binary Search Tree against the following header – do not change it:

#ifndef BST_H
#define BST_H

class TreeNode
{
public:
    // Pointer to the left child
    TreeNode *left = nullptr;
    // Pointer to the right child
    TreeNode *right = nullptr;
    // Value in the node
    int value;

    // Constructor, sets the value
    TreeNode(int v) : value(v) {}
    // Destructor
    ~TreeNode() {}
};

class Tree
{
public:
    TreeNode *root = nullptr;

    // Public interface to the recursive functions below
    void insert(int value);

    bool contains(int value);
    int min();
    int max();
    int depth(int value);

    void preOrderTraversal();
    void inOrderTraversal();
    void postOrderTraversal();
    void levelOrderTraversal();

    void remove(int value);

    ~Tree();

private:
    // These functions do the actual work
    void insert(int v, TreeNode *&subtree);

    bool contains(int value, TreeNode *subtree) const;
    int min(TreeNode *subtree) const;
    int max(TreeNode *subtree) const;
    int depth(int value, TreeNode *subtree) const;

    void preOrderTraversal(TreeNode *subtree) const;
    void inOrderTraversal(TreeNode *subtree) const;
    void postOrderTraversal(TreeNode *subtree) const;
    void levelOrderTraversal(TreeNode *subtree) const;

    void remove(int value, TreeNode *&subtree);
};

#endif // BST_H

Notice that almost every operation comes in two versions: a public one with no extra arguments (e.g. bool contains(int value);), and a private one that takes an extra TreeNode *subtree parameter (e.g. bool contains(int value, TreeNode *subtree) const;). This is the standard pattern for writing recursive tree functions. The public version is the external interface – it’s what the unit tests (and the rest of your code) actually call, and it doesn’t need to know anything about root or how the tree is represented internally. The private version is where the real recursive work happens, walking down subtree one level at a time. All the public version has to do is kick off the recursion at root, for example:

bool Tree::contains(int value){
    return contains(value, root);
}

All of the public functions above are already provided for you – you only need to implement the private version of each one. The one exception is insert, which you don’t need to implement at all: it’s fully worked below, so you can see the pattern before writing the rest yourself.

void Tree::insert(int v, TreeNode *&subtree){
    if(subtree == nullptr){
        subtree = new TreeNode(v);
    }else if(v < subtree->value){
        insert(v, subtree->left);
    }else{
        insert(v, subtree->right);
    }
}

Throughout the rest of this lab we’ll use the same example tree, built by inserting 50, 30, 35, 61, 24, 58, 62, 32 in that order:

                50
              /    \
            30      61
           /  \     /  \
          24  35   58  62
              /
             32

8.5.2 `contains`

Implement contains, which should return true if value is anywhere in the tree, and false otherwise. For example, on the tree above, contains(58) should return true and contains(59) should return false.

8.5.3 `min` and `max`

Implement min and max, which return the smallest and largest values stored in the tree. On the tree above, min() should return 24 and max() should return 62. Remember that in a BST the minimum is always the left-most node and the maximum is always the right-most node – you never need to look at every node to find them.

8.5.4 `depth`

Implement depth, which returns the depth of the node containing value: the number of edges on the path from the root down to that node. The root has depth 0, its children have depth 1, and so on. If value isn’t in the tree, return -1.

The path from the root to a node is exactly the path you follow when you search for its value – so depth is really contains with a counter. On the tree above, depth(50) is 0, depth(61) is 1, depth(35) is 2, depth(32) is 3, and depth(59) is -1.

💡 Hint

Like the other functions, depth has a natural recursive definition. The depth of value in a subtree is:

depth(value, subtree):
    if subtree is empty:            return -1       (not found)
    if value == subtree's value:    return 0        (found it here)
    d = depth(value, the left or right child)       (whichever the search goes down)
    if d == -1:                     return -1       (not found further down either)
    return d + 1                                    (one more edge from this node)

Each recursive call moves one level further down the search path, so every level we step down adds one to the answer.

The widget below steps through exactly this calculation on the example tree: follow the search path down, then watch the return values come back up. Try a missing value too, to see why the -1 check matters.

Open in new tab ↗

8.5.5 Traversals

Implement preOrderTraversal, inOrderTraversal, and postOrderTraversal. Each one visits every node in the tree exactly once, but in a different order:

Pre-order (root, left, right): 50 30 24 35 32 61 58 62
In-order (left, root, right): 24 30 32 35 50 58 61 62 – notice this comes out in sorted order! That will always be true for a valid BST.
Post-order (left, right, root): 24 32 35 30 58 62 61 50

Since these functions return void, the unit tests check them by capturing what gets printed rather than a returned value. As you visit each node, print its value with cout <<, exactly the way you always have – followed by a space, the same as the examples above (a trailing space at the end of the line is fine). The same applies to levelOrderTraversal below.

Before writing the recursive code, it’s worth practicing reading traversal orders off a tree by hand – see the practice widget just before this lab.

8.5.5.1 Level-Order Traversal

Then implement levelOrderTraversal, which visits the nodes level by level, from top to bottom and left to right – rather than following the left/right recursion used by the other traversals. On the tree above, this should visit the nodes in the order 50 30 61 24 35 58 62 32.

💡 Hint

levelOrderTraversal doesn’t recurse the way the other traversals do – it’s usually written iteratively using a std::queue<TreeNode*>. At a high level:

create an empty queue of TreeNode*
push root onto the queue

while the queue is not empty:
    take the node at the front of the queue, and remove it
    visit that node's value
    if it has a left child, push the left child onto the queue
    if it has a right child, push the right child onto the queue

8.5.6 `remove`

Last of all, implement remove, which deletes value from the tree (if it is present) while keeping the rest of the tree a valid binary search tree. There are three cases to handle, depending on the node being removed:

No children – simply delete the node.
One child – replace the node with its child.
Two children – find the node’s in-order successor (the smallest value in its right subtree), copy that value into the node, and then remove the successor from the right subtree instead.

For example, removing 30 from the tree above is a two-child case, and should leave you with a tree whose in-order traversal is still 24 32 35 50 58 61 62.

Finally, don’t forget to implement ~Tree() so that it recursively deletes every node in the tree. This generally isn’t checked directly by the unit tests, but it’s good practice, and you’ll want it if you write your own tests without leaking memory.

8.6 Additional Reading

Great BST Visualisation: https://www.cs.usfca.edu/~galles/visualization/BST.html
Geeks for Geeks - Binary Trees: https://www.geeksforgeeks.org/binary-tree-data-structure
Geeks for Geeks - Binary Search Trees: https://www.geeksforgeeks.org/binary-search-tree-data-structure
Chapter 4 – Weiss (2014)
Chapter 7 – Goodrich et al. (2011)
Chapter 8 – Dale et al. (2018)
MIT OpenCourseware, Binary Search Trees: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-5-binary-search-trees-bst-sort/

References

Dale, Nell B, Chip Weems, and Tim Richards. 2018. C++ Plus Data Structures. 6th ed. Jones & Bartlett Learning.

Goodrich, Michael T, Roberto Tamassia, and David M Mount. 2011. Data Structures and Algorithms in c++. 2nd ed. John Wiley & Sons.

Weiss, Mark A. 2014. Data Structures & Algorithm Analysis in c++. 4th ed. Pearson Education.

Literally, exponential speedup in the mathematical sense: \(2^{log_2n} = n\)↩︎

Introduction to Data Structures & Algorithms

Chapter 8 Binary Search Trees

8.1 Trees

8.2 Binary Trees

8.3 Binary Search Tree

8.3.1 Insertion

8.3.2 Searching

8.3.3 Min & Max

8.3.4 Delete

8.4 Tree Traversals

8.4.1 Depth First Traversals

8.4.2 Breadth-First or Level Traversals

8.4.3 Practice

8.5 Lab: Binary Search Trees

8.5.1 The Header

8.5.2 `contains`

8.5.3 `min` and `max`

8.5.4 `depth`

8.5.5 Traversals

8.5.5.1 Level-Order Traversal

8.5.6 `remove`

8.6 Additional Reading

References

Chapter 8 Binary Search Trees

8.1 Trees

8.2 Binary Trees

8.3 Binary Search Tree

8.3.1 Insertion

8.3.2 Searching

8.3.3 Min & Max

8.3.4 Delete

8.4 Tree Traversals

8.4.1 Depth First Traversals

8.4.2 Breadth-First or Level Traversals

8.4.3 Practice

8.5 Lab: Binary Search Trees

8.5.1 The Header

8.5.2 contains

8.5.3 min and max

8.5.4 depth

8.5.5 Traversals

8.5.5.1 Level-Order Traversal

8.5.6 remove

8.6 Additional Reading

References

8.5.2 `contains`

8.5.3 `min` and `max`

8.5.4 `depth`

8.5.6 `remove`