binary-search-tree.asc

Binary Search Tree

To recap, the Binary Search Tree (BST) is a tree data structure that keeps the following constraints:

• Each node must have at most two children. Usually referred to as "left" and "right."

• All trees must have a "root" node.

• The order of nodes values must be: left child < parent < right child.

• Nodes might need re-ordering after each insert/delete operation to keep the left ⇐ parent < right constraint.

Implementing a Binary Search Tree

The first step is to implement the Binary Tree Node, which can hold 0, 1, or 2 children.

Binary Tree Node’s constructor

link:../../../src/data-structures/trees/binary-tree-node.js[role=include]
  }
}

Does this look familiar to you? It’s almost like the linked list node, but instead of having next and previous, it has left and right. That guarantees that we have at most two children.

We also added the meta object to hold some metadata about the node, like duplicity, color (for red-black trees), or any other data needed for future algorithms.

We implemented the node; now, let’s layout other methods that we can implement for a BST:

Binary Search Tree’s class

link:../../../src/data-structures/trees/binary-search-tree.js[role=include]

  add(value) { /* ... */ }
  find(value) { /* ... */ }
  remove(value) { /* ... */ }
  getMax() { /* ... */ }
  getMin() { /* ... */ }
}

With the methods add and remove, we have to guarantee that our tree always has one root element from where we can navigate left or right based on the value we are looking for. Let’s implement those add method first:

Inserting new elements in a BST

For inserting an element in a BST, we have two scenarios:

1. If the tree is empty (root element is null), we add the newly created node as root, and that’s it!

2. If the tree has a root, compare the new value with the root. Then we have three possibilities:

   1. root == newValue: we increase the duplicity counter in that case, and done!

   2. root > newValue, we search on the left side of the root.

   3. root < newValue, we search on the right side of the root.

3. Repeat the comparison between the current node and newValue, until we find the value or (null) space.

For instance, let’s say that we want to insert the values 19, 21, 10, 2, 18 in a BST:

Figure 1. Inserting values on a BST.

In the last box of the image above, we start by the root when we insert node 18 (19). Since 18 is less than 19, then we move left. Node 18 is greater than 10, so we move right. There’s an empty spot, and we place it there. Let’s code it up:

Binary Search Tree’s class

link:../../../src/data-structures/trees/binary-search-tree.js[role=include]

1. We are using a helper function findNodeAndParent to iterate through the tree, finding a node with the current value “found” and its parent (implementation on the next section).

2. We are taking care of duplicates. Instead of inserting duplicates, we are keeping a multiplicity tally. We have to decrease it when removing nodes.

Finding a value in a BST

We can implement the find method using the helper findNodeAndParent as follows:

Binary Search Tree’s find methods

link:../../../src/data-structures/trees/binary-search-tree.js[role=include]

findNodeAndParent is a recursive function that goes to the left or right child, depending on the value. However, if the value already exists, it will return it in found variable.

Removing elements from a BST

Deleting a node from a BST has three cases.

The node is a

1. leaf

2. parent with one child

3. parent with two children/root.

Removing a leaf (Node with 0 children)

Deleting a leaf is the easiest; we look for their parent and set the child to null.

Figure 2. Removing node without children from a BST.

Node 18, will be hanging around until the garbage collector is run. However, there’s no node referencing to it to no longer be reachable from the tree.

Removing a parent (Node with 1 children)

Removing a parent is not as easy since you need to find new parents for its children.

Figure 3. Removing node with 1 children from a BST.

In the example, we removed node 10 from the tree, so its child (node 2) needs a new parent. We made node 19 the new parent for node 2.

Removing a full parent (Node with 2 children) or root

Removing a parent of two children is the trickiest of all cases because we need to find new parents. (This sentence might sound tragic out of context 😂)

Figure 4. Removing node with two children from a BST.

In the example, we delete the root node 19. This deletion leaves two orphans (node 10 and node 21). There are no more parents because node 19 was the root element. One way to solve this problem is to combine the left subtree (Node 10 and descendants) into the right subtree (node 21). The final result is node 21 is the new root.

What would happen if node 21 had a left child (e.g., node 20)? Well, we would move node 10 and its descendants' bellow node 20.

Implementing removing elements from a BST

All the described scenarios removing nodes with zero, one and two children can be sum up on this code:

Binary Search Tree’s remove method

link:../../../src/data-structures/trees/binary-search-tree.js[role=include]

1. Try to find if the value exists on the tree.

2. If the value doesn’t exist, we are done!

3. Create a new subtree without the value to delete

4. Check the multiplicity (duplicates) and decrement the count if we have multiple nodes with the same value

5. If the nodeToRemove was the root, we wouldwould move the removed node’s children as the new root.

6. If it was not the root, we will go to the deleted node’s parent and put their children there.

We compute removedNodeChildren, which is the resulting subtree after combining the deleted node children.

The method to combine subtrees is the following:

BST’s combine subtrees

link:../../../src/data-structures/trees/binary-search-tree.js[role=include]

Take a look at the code above and the example. You will see how to remove node 30 and combine both children’s subtree, and keeping the BST rules. Also, this method uses a helper to get the left-most node. We can implement it like this:

Binary Search Tree’s get the leftmost node

link:../../../src/data-structures/trees/binary-search-tree.js[role=include]

That’s all we need to remove elements from a BST. Check out the complete BST implementation here.

Differentiating a balanced and non-balanced Tree

As we insert and remove nodes from a BST, we could end up like the tree on the left:

Figure 5. Balanced vs. Unbalanced Tree.

The tree on the left is unbalanced. It looks like a Linked List and has the same runtime! Searching for an element would be O(n), yikes! However, on a balanced tree, the search time is O(log n), which is pretty good! That’s why we always want to keep the tree balanced. In further chapters, we will explore how to keep a tree balanced after each insert/delete.

Tree Complexity

We can sum up the tree operations using Big O notation:

Table 1. Time complexity for a Binary Search Tree (BST)

Data Structure	Searching By		Insert	Delete	Space Complexity
	Index/Key	Value
BST (unbalanced)	-	O(n)	O(n)	O(n)	O(n)
BST (balanced)	-	O(log n)	O(log n)	O(log n)	O(n)