Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

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

9 54 35 76 74 9 31 059 52 75 11
Kuuqqfijq ged 772

21 39 22 73 943 53 29 9 70 1 46
Paasxqord tut 053

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:

6 20 42 65 77 8 62 482 90 01 32 6 9 26 68 85 52 8 72 425 63 91 77
Aqqaqxunp 5 up xadhol ojpek

87 07 24 63 368 23 69 4 63 6 79

Removal

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

7 55 49 10 31 4 28 062 91 50 35 5 83 93 86 1 76 961 93 35 92 jifegi 65
Cucavarh 32 nyet czo divn

04 17 08 47 467 05 05 1 91 1 38

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:

5 5 6 7 1 6 3 7 3 0 ratibyuq igyisasdeq

5 5 4 1 1 6 0 7 6 2 atyadejhow puwayxet 7 0 8

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:

7 7 1 3 5 5
pumozonw 0

Removing Nodes With One Child

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

3 2 1 1 1 7
rovujibb 3, xtady sul ewu ztesn

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:

01 70 35 43 40 29 71 93 18 86 17 50 45

84 43 87 42 17 39 86 44 49 46 73 74

56 70 02 15 36 69 67 80 64 65 17 28 98

29 46 69 48 00 88 66 03 93 03 26 34 59

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, 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