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 a 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 that 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 root is not null. Start from it and compare the node’s value against the new element. If the node has higher than a new item, we move to the right child, otherwise to the left. We check each node recursively until we find an empty spot where we can put the new element and keep the rule right < parent < left.

3. If we insert the same value multiple times, we don’t want duplicates. So, we can keep track of multiples using a duplicity counter.

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

Figure 1. Inserting values on a BST.

In the last box of the image above, when we are inserting node 18, we start by the root (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 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 child or right 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 have 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 so it won’t be reachable from the tree anymore.

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 for two children. (This sentence sounds 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 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, then we move the removed node’s children as the new root.

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

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

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 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 are going to 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)