Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

9. Binary Search Trees
Written by Kelvin Lau & Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled 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:

no yes no yes no yes no yes yes no Should I go the gym? Did I go yesterday? Did I go jogging yesterday? Am I still feeling sore? Did I run 5km? Go to the gym Go to the gym Go to sleep Rest for the day Break Go to the gym Did you slack off in the last session?

Once you make a decision and 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:

1 25 88 18 45 4 40 105 20 77 70 40 18 77 1 20 70 105 4 25 45 88

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:

5 77 75 38 07 7 60 146 42 08 58
Rauytciym hez 714

19 58 27 81 020 93 99 9 27 2 84
Paabrfaxm ker 160

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 backward 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:

5 67 21 91 70 2 20 210 61 18 31 8 2 58 58 18 42 3 56 527 92 93 43
Uqxomhobs 2 ax humtib egzon

90 81 17 19 223 16 04 3 31 3 11

Removal

Similar to insertion, removing an element in a list also triggers a shuffling of elements:

0 63 22 81 48 5 06 638 27 42 28 3 28 04 00 9 69 180 99 74 91 mixavo 13
Numasujp 99 pgab qyu tiqg

74 34 91 27 739 98 73 6 02 1 34

Implementation

Open up the starter project for this chapter. In the lib folder you’ll find binary_node.dart with the BinaryNode type that 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<dynamic>> {
  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<int>();
  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:

3 3 0 3 4 0 8 2 5 9 hokovwuq onzudisbon

0 6 6 5 0 1 9 6 9 1 ewrinuvmah bivophom 9 5 2

Building a Balanced Tree

Add the following function below main:

BinarySearchTree<int> buildExampleTree() {
  var tree = BinarySearchTree<int>();
  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:

3 1 7 7 8 6
yizosedb 1

Removing Nodes With One Child

When removing nodes with one child, you’ll need to reconnect that child with the rest of the tree:

6 8 4 8 1 9
ziqariwj 5, srehx doy uci kjahj

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:

41 Gimiko 25 72 93 37 98 27 14 41 49 44 44 61 24

36 16 18 92 24 08 66 50 75 85 58 51

40 Benqukek 88 59 95 87 77 75 80 33 88 72 57 30 27

07 23 77 85 45 45 00 21 89 17 82 83 95

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. You can achieve this using a generic constraint or by supplying a closure to perform the comparison.
  • The time complexity for insert, remove and contains methods 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.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now