Chapters

Hide chapters

Data Structures & Algorithms in Kotlin

First Edition · Android 10 · Kotlin 1.3 · IDEA

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

8. Binary Search Trees
Written by Irina Galata, Kelvin Lau and Vincent Ngo

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 of the possibilities of the other side, cutting the problem in half.

Once you make a decision and choose a branch, there’s 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 this property 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 arrays and linked lists.

In this chapter, you’ll learn about the benefits of the BST relative to an array and implement the data structure from scratch.

Case study: array vs. BST

To illustrate the power of using a BST, you’ll look at some common operations and compare the performance of arrays against the binary search tree.

Consider the following two collections:

Lookup

There’s only one way to do element lookups for an unsorted array. You need to check every element in the array from the start.

Searching for 105
Kuevbwozm wuf 925

Searching for 105
Reelycird xas 386

Insertion

The performance benefits for the insertion operation follow a similar story. Assume you want to insert 0 into a collection.

Inserting 0 in sorted order
Uczethucy 5 uj nowhuv eyxit

Removal

Similar to insertion, removing an element from an array also triggers a shuffling of elements.

Removing 25 from the array
Quzonixs 96 pfuv mvi efver

Implementation

Open the starter project for this chapter. In it, you’ll find the BinaryNode class you created in the previous chapter. Create a new file named BinarySearchTree.kt and add the following to it:

class BinarySearchTree<T: Comparable<T>>() {

  var root: BinaryNode<T>? = null

  override fun toString() = root?.toString() ?: "empty tree"

}

Inserting elements

Following the rules of the BST, nodes of the left child must contain values less than the current node, whereas nodes of the right child must contain values greater than or equal to the current node. You’ll implement insert while respecting these rules.

fun insert(value: T) {
  root = insert(root, value)
}

private fun insert(
    node: BinaryNode<T>?,
    value: T
): BinaryNode<T> {
  // 1
  node ?: return BinaryNode(value)
  // 2
  if (value < node.value) {
    node.leftChild = insert(node.leftChild, value)
  } else {
    node.rightChild = insert(node.rightChild, value)
  }
  // 3
  return node
}
"building a BST" example {
  val bst = BinarySearchTree<Int>()
  (0..4).forEach {
    bst.insert(it)
  }
  println(bst)
}
---Example of building a BST---
   ┌──4
  ┌──3
  │ └──null
 ┌──2
 │ └──null
┌──1
│ └──null
0
└──null

val exampleTree = BinarySearchTree<Int>().apply {
  insert(3)
  insert(1)
  insert(4)
  insert(0)
  insert(2)
  insert(5)
}
"building a BST" example {
  println(exampleTree)
}
---Example of building a BST---
 ┌──5
┌──4
│ └──null
3
│ ┌──2
└──1
 └──0

Finding elements

Finding an element in a BST 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.

fun contains(value: T): Boolean {
  root ?: return false

  var found = false
  root?.traverseInOrder {
    if (value == it) {
      found = true
    }
  }

  return found
}
"finding a node" example {
  if (exampleTree.contains(5)) {
    println("Found 5!")
  } else {
    println("Couldn't find 5")
  }
}
---Example of finding a node---
Found 5!

Optimizing contains

You can rely on the rules of the BST to avoid needless comparisons. Inside BinarySearchTree.kt, update contains to the following:

fun contains(value: T): Boolean {
  // 1
  var current = root

  // 2
  while (current != null) {
    // 3
    if (current.value == value) {
      return true
    }

    // 4
    current = if (value < current.value) {
      current.leftChild
    } else {
      current.rightChild
    }
  }

  return false
}

Removing elements

Removing elements is a little more tricky, as there are a few different scenarios you need to handle.

Case 1: Leaf node

Removing a leaf node is straightforward; simply detach the leaf node.

Removing 2
Vutivufl 1

Case 2: Nodes with one child

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

Removing 4, which has 1 child
Kejutovj 3, kyicp ros 3 wheld

Case 3: Nodes with two children

Nodes with two children are a bit more complicated, so a more complex example tree will serve better to illustrate how to handle this situation. Assume that you have the following tree and that you want to remove the value 25:

Implementation

Add the following code to BinaryNode.kt:

val min: BinaryNode<T>?
  get() = leftChild?.min ?: this
fun remove(value: T) {
  root = remove(root, value)
}

private fun remove(
    node: BinaryNode<T>?,
    value: T
): BinaryNode<T>? {
  node ?: return null

  when {
    value == node.value -> {
      // more to come
    }
    value < node.value -> node.leftChild = remove(node.leftChild, value)
    else -> node.rightChild = remove(node.rightChild, value)
  }
  return node
}
// 1
if (node.leftChild == null && node.rightChild == null) {
  return null
}
// 2
if (node.leftChild == null) {
  return node.rightChild
}
// 3
if (node.rightChild == null) {
  return node.leftChild
}
// 4
node.rightChild?.min?.value?.let {
  node.value = it
}

node.rightChild = remove(node.rightChild, node.value)
"removing a node" example {
  println("Tree before removal:")
  println(exampleTree)
  exampleTree.remove(3)
  println("Tree after removing root:")
  println(exampleTree)
}
---Example of removing a node---
Tree before removal:
 ┌──5
┌──4
│ └──null
3
│ ┌──2
└──1
 └──0

Tree after removing root:
┌──5
4
│ ┌──2
└──1
 └──0

Challenges

Think you have searching of binary trees down cold? Try out these three challenges to lock down the concepts.

Challenge 1 : Is it a BST?

Create a function that checks if a binary tree is a binary search tree.

Solution 1

A binary search tree is a tree where every left child is less than or equal to its parent, and every right child is greater than its parent. An algorithm that verifies whether a tree is a binary search tree involves going through all the nodes and checking for this property.

val isBinarySearchTree: Boolean
  get() = isBST(this, min = null, max = null)
  
// 1
private fun isBST(tree: BinaryNode<T>?, min: T?, max: T?): Boolean {
  // 2
  tree ?: return true

  // 3
  if (min != null && tree.value <= min) {
    return false
  } else if (max != null && tree.value > max) {
    return false
  }
  
  // 4
  return isBST(tree.leftChild, min, tree.value) && isBST(tree.rightChild, tree.value, max)
}

Challenge 2 : Equality between BSTs

Override equals() to check whether two binary search trees are equal.

Solution 2

Overriding equals() is relatively straightforward. For two binary trees to be equal, both trees must have the same elements in the same order. This is how the solution looks:

// 1
override fun equals(other: Any?): Boolean {
  // 2
  return if (other != null && other is BinaryNode<*>) {
    this.value == other.value &&
        this.leftChild == other.leftChild &&
        this.rightChild == other.rightChild
  } else {
    false
  }
}
class BinaryNode<T: Comparable<T>>(var value: T)

Challenge 3 : BSTs with same elements?

Create a method that checks if the current tree contains all of the elements of another tree.

Solution 3

Your goal is to create a method that checks if the current tree contains all of the elements of another tree. In other words, the values in the current tree must be a superset of the values in the other tree. The solution looks like this:

fun contains(subtree: BinarySearchTree<T>): Boolean {
  // 1
  val set = mutableSetOf<T>()
  root?.traverseInOrder {
    set.add(it)
  }

  // 2
  var isEqual = true
  subtree.root?.traverseInOrder {
    isEqual = isEqual && set.contains(it)
  }
  return isEqual
}

Key points

  • The binary search tree is a powerful data structure for holding sorted data.
  • Average performance for insert, remove and contains in a BST is O(log n).
  • Performance will degrade to O(n) as the tree becomes unbalanced. This is undesirable, so you’ll learn about a self-balancing binary search tree known as the AVL tree in the next chapter.
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