Binary Search Trees

 We’ve covered that a binary tree is a special kind of tree, in which each node splits into exactly 0, 1, or 2 others—and never more. We’ve also initially seen binary search done on an array: go to the middle index, decide which half, discard the “wrong” one, go to the middle, decide which half, etc., and keep doing this recursively until either you can prove that you’ve found the element you want, or that it definitely isn’t in your collection.

Now, let’s take those ideas and merge them: create a tree purporpse-built to execute binary search.  

Remember that one of the conditions for binary search to work—as opposed to the simpler linear search—is that the contents of the array (now a tree) need to be sorted.

When something is sorted, it helps to keep an eye on 3 reference points: the first element, the median element (half are “less/before” and half are “greater/after”), and the last element. (Which of the first versus last is the biggest and which is the smallest, of course, depends on the direction of the sort—ascending or descending.)

Knowing how a binary tree works, where would these three values go?

·       The median has half the data set to its left and half the data set to its right

·       The min has all the rest of the data set to its right

·       The max has all the rest of the data set to its left

Take a moment to pause, draw out a tree, and think about where these values should go.

Let’s start with the median, because this value actually occupies a special place. Where is the “center of gravity” (this isn’t a real term) of the tree? Naturally, the root—half of the data less than it is in the left subtree, and half of the data greater than it is in the right subtree!

Where then do the min and max live? Let’s start with the min. The min occupies the place that takes a left at every fork from the root (graphically, as far to the bottom left as possible). Likewise, the max takes a right at every fork from the root (and therefore is found as far to the bottom right as possible).

Suppose this is our tree:

How did we build it?

• 8 becomes the root
• Then we add 3
• 3 < 8, so go left
• Then we add 1
• 1 < 8, so go left
• 1 < 3, so go left
• Then we add 6
• 6 < 8, so go left
• 6 > 3, so go right
• Then we add 4
• 4 < 8, so go left
• 4 > 3, so go right
• 4 < 6, so go left
• Then we add 7
• 7 < 8, so go left
• 7 > 3, so go right
• 7 > 6, so go right
• Then we add 10
• 8 > 10, so go right
• Then we add 14
• 14 > 8, so go right
• 14 > 10, so go right
• Then we add 13
• 13 > 8, so go right
• 13 > 10, so go right
• 13 < 14, so go left

To add 0 and 20:

Adding 0:

• 0 < 8, so go left
• 0 < 3, so go left
• 0 < 1, so go left

Adding 20:

• 20 > 8, so go right
• 20 > 10, so go right
• 20 > 14, so go right

Here is that process in pseudocode:

function insert(node, key):

    if node is null:

        return new Node(key)

 

    if key < node.value:

        node.left = insert(node.left, key)

    else if key > node.value:

        node.right = insert(node.right, key)

    // If key == node.value, do nothing, or handle duplicates as needed

 

    return node

 

Adding nodes in this way is easy, but how about removing, with the caveat that a binary search tree, as its name implies, is used for binary search, which requires a sorted data set?

We find ourselves in one of 3 cases:

• The node to remove is a leaf, i.e., has no children—this is trivial
• The node to remove is an interior node, i.e., having both children and parents
• The node to remove is the root, i.e., having no parents, but having children

 

Here is the pseudocode for the removal of an interior node:

function deleteNode(root, key):

    if root is null:

        return null

 

    if key < root.value:

        root.left = deleteNode(root.left, key)

    else if key > root.value:

        root.right = deleteNode(root.right, key)

    else:

        // Node found

        if root.left is null:

            temp = root.right

            free(root)

            return temp

        else if root.right is null:

            temp = root.left

            free(root)

            return temp

        else:

            // Node has two children

            successor = findMin(root.right)

            root.value = successor.value

            root.right = deleteNode(root.right, successor.value)

    return root

 

function findMin(node):

    while node.left is not null:

        node = node.left

    return node

and here is the pseudocode to remove the root:

function deleteRoot(root):

    if root is null:

        return null

 

    // Case 1: Root has no children (tree becomes empty)

    if root.left is null and root.right is null:

        free(root)

        return null

 

    // Case 2: Root has only one child

    if root.left is null:

        temp = root.right

        free(root)

        return temp

    if root.right is null:

        temp = root.left

        free(root)

        return temp

 

    // Case 3: Root has two children

    // Find inorder successor (smallest in right subtree)

    successor = findMin(root.right)

    root.value = successor.value

    root.right = deleteNode(root.right, successor.value)

    return root

 

function findMin(node):

    while node.left is not null:

        node = node.left

    return node