10.
Binary Search Trees
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
A binary search tree, or BST, is a data structure that facilitates fast lookup, insert and removal operations. Consider the following decision tree where picking a side forfeits all the possibilities of the other side, cutting the problem in half:
Once choose a branch, there is no looking back. You keep going until you make a final decision at a leaf node. Binary trees let you do the same thing. Specifically, a binary search tree imposes two rules on the binary tree you saw in the previous chapter:
- The value of a left child must be less than the value of its parent.
- Consequently, the value of a right child must be greater than or equal to the value of its parent.
Binary search trees use these properties to save you from performing unnecessary checking. As a result, lookup, insert and removal have an average time complexity of O(log n), which is considerably faster than linear data structures such as lists and linked lists.
In this chapter, you’ll learn about the benefits of BST relative to a list and, as usual, implement the data structure from scratch.
List vs. BST
To illustrate the power of using BST, you’ll look at some common operations and compare the performance of lists against the binary search tree.
Consider the following two collections:
Lookup
There’s only one way to do element lookups for an unsorted list. You need to check every element in the list from the start:
Insertion
The performance benefits for the insertion operation follow a similar story. Assume you want to insert 0 into a collection. Inserting at the front of the list causes all other elements to shift backwards by one position. It’s like butting in line. Everyone in the line behind your chosen spot needs to make space for you by shuffling back:
Removal
Similar to insertion, removing an element in a list also triggers a shuffling of elements:
Implementation
Open up the starter project for this chapter. In the lib folder, you’ll find binary_node.dart with the BinaryNode type you created in the previous chapter. Create a new file named binary_search_tree.dart in the same folder and add the following code to it:
import 'binary_node.dart';
class BinarySearchTree<E extends Comparable<E>> {
BinaryNode<E>? root;
@override
String toString() => root.toString();
}
Inserting Elements
In accordance with BST rules, nodes of the left child must contain values less than the current node. Nodes of the right child must contain values greater than or equal to the current node. You’ll implement the insert method while respecting these rules.
Adding an Insert Method
Add the following to BinarySearchTree:
void insert(E value) {
root = _insertAt(root, value);
}
BinaryNode<E> _insertAt(BinaryNode<E>? node, E value) {
// 1
if (node == null) {
return BinaryNode(value);
}
// 2
if (value.compareTo(node.value) < 0) {
node.leftChild = _insertAt(node.leftChild, value);
} else {
node.rightChild = _insertAt(node.rightChild, value);
}
// 3
return node;
}
Testing it Out
Open bin/starter.dart and replace the contents with the following:
import 'package:starter/binary_search_tree.dart';
void main() {
final tree = BinarySearchTree<num>();
for (var i = 0; i < 5; i++) {
tree.insert(i);
}
print(tree);
}
┌── 4
┌──3
│ └── null
┌──2
│ └── null
┌──1
│ └── null
0
└── null
Balanced vs. Unbalanced Trees
The previous tree looks a bit unbalanced, but it does follow the rules. However, this tree layout has undesirable consequences. When working with trees, you always want to achieve a balanced format:
Building a Balanced Tree
Add the following function below main:
BinarySearchTree<int> buildExampleTree() {
var tree = BinarySearchTree<num>();
tree.insert(3);
tree.insert(1);
tree.insert(4);
tree.insert(0);
tree.insert(2);
tree.insert(5);
return tree;
}
final tree = buildExampleTree();
print(tree);
┌── 5
┌──4
│ └── null
3
│ ┌── 2
└──1
└── 0
Finding Elements
Finding an element in a binary search tree requires you to traverse through its nodes. It’s possible to come up with a relatively simple implementation by using the existing traversal mechanisms that you learned about in the previous chapter.
bool contains(E value) {
if (root == null) return false;
var found = false;
root!.traverseInOrder((other) {
if (value == other) {
found = true;
}
});
return found;
}
final tree = buildExampleTree();
if (tree.contains(5)) {
print("Found 5!");
} else {
print("Couldn’t find 5");
}
Found 5!
Optimizing contains
Relying on the properties of BST can help you avoid needless comparisons. Back in BinarySearchTree, replace contains with the following:
bool contains(E value) {
// 1
var current = root;
// 2
while (current != null) {
// 3
if (current.value == value) {
return true;
}
// 4
if (value.compareTo(current.value) < 0) {
current = current.leftChild;
} else {
current = current.rightChild;
}
}
return false;
}
Removing Elements
Removing elements is a little more tricky because you need to handle a few different scenarios.
Removing a Leaf Node
Removing a leaf node is straightforward. Simply detach the leaf node:
Removing Nodes With One Child
When removing nodes with one child, you’ll need to reconnect that child with the rest of the tree:
Removing Nodes With Two Children
Nodes with two children are a bit more complicated, so a more complex example tree will better illustrate how to handle this situation. Assume that you have the following tree and that you want to remove the value 25:
Finding the Minimum Node in a Subtree
Open up binary_search_tree.dart. You’ll implement the remove method in just a minute, but first add the following helper extension at the bottom of the file:
extension _MinFinder<E> on BinaryNode<E> {
BinaryNode<E> get min => leftChild?.min ?? this;
}
Implementing remove
Now add these two methods to BinarySearchTree:
void remove(E value) {
root = _remove(root, value);
}
BinaryNode<E>? _remove(BinaryNode<E>? node, E value) {
if (node == null) return null;
if (value == node.value) {
// more to come
} else if (value.compareTo(node.value) < 0) {
node.leftChild = _remove(node.leftChild, value);
} else {
node.rightChild = _remove(node.rightChild, value);
}
return node;
}
Handling the Removal Cases
Replace the // more to come comment above with the following code:
// 1
if (node.leftChild == null && node.rightChild == null) {
return null;
}
// 2
if (node.leftChild == null) {
return node.rightChild;
}
if (node.rightChild == null) {
return node.leftChild;
}
// 3
node.value = node.rightChild!.min.value;
node.rightChild = _remove(node.rightChild, node.value);
Testing it Out
Head back to main and test remove by writing the following:
final tree = buildExampleTree();
print('Tree before removal:');
print(tree);
tree.remove(3);
print('Tree after removing root:');
print(tree);
Tree before removal:
┌── 5
┌──4
│ └── null
3
│ ┌── 2
└──1
└── 0
Tree after removing root:
┌── 5
4
│ ┌── 2
└──1
└── 0
Challenges
Think you’ve gotten the hang of binary search trees? Try out these three challenges to lock the concepts down. As usual, you can find the answers in the Challenge Solutions section at the end of the book.
Challenge 1: Binary Tree or Binary Search Tree?
Write a function that checks if a binary tree is a binary search tree.
Challenge 2: Equality
Given two binary trees, how would you test if they are equal or not?
Challenge 3: Is it a Subtree?
Create a method that checks if the current tree contains all the elements of another tree.
Key Points
- The binary search tree (BST) is a powerful data structure for holding sorted data.
- Elements of the binary search tree must be comparable.
- The time complexity for
insert,removeandcontainsmethods in a BST is O(log n). - Performance will degrade to O(n) as the tree becomes unbalanced. This is undesirable, but self-balancing trees such as the AVL tree can overcome the problem.