# Binary Search Trees

## Trees

The data structures we have used so far have been linear by nature. Arrays, linked lists, stacks and queues all have a definite start and end. Today we will look at a type of data structure, the tree, for which this is not the case.

Unlike organic trees, the tree data structure is normally drawn upside down, with the root at the top and leaves at the bottom. There are a few different terms used when discussing trees:

• Node: As with linked lists, a node is simply one element of the tree.
• Root: The root node of a tree is the very topmost node.
• Child: A node is a child of another node if it is below the other and there is a line directly connecting them.
• Parent: A node is a parent of another node if it is above the other and there is a line directly connecting them.
• Leaf: A leaf node is one that has no children.
• Subtree: A subtree is a section of the tree that is a complete tree in its own right, except that its root has a parent.
• Height: The height of the tree is the longest line of nodes from the root to leaf. The height of the above tree is 4.

Trees are naturally recursive data structures. Each subtree can be treated as a full tree allowing us to write recursive functions that deal with trees.

There are many different types of trees which are used for many different applications. Trees are used as the basis for file system and database implementations. They are used for implementing compilers and interpreters. They are also generally useful any time we want to store hierarchical data.

## Binary Trees

A binary tree is a type of tree where every node can have at most two children nodes. The two children are typically called the left and right children.

When we are using binary trees inside of a program, we typically create a class for storing the nodes:


// a node in a tree has data, and a left and right subtree
class Node {
int data;
Node left;
Node right;
}


When we did linked lists, we used a node definition similar to the above. The difference for a binary tree is how we will set up our structure. When we create nodes, we will fill in the left and right references such that they refer to children nodes of the tree.

Note that a node can have either or both children references set to null. If both are set to null, than that node is a leaf.

This example demonstrates constructing a binary tree by setting the nodes up directly in code. The tree that this program constructs looks like this:

## Traversals

With the data structures we have seen so far, looping through each item has been fairly easy. With an array, linked list, or any other kind of linear data structure, there are really only two ways to do, either forwards or backwards.

A tree, however, presents more of a challenge. Where should we start and where should we end? "Looping through" a tree is called traversing it. As we traverse a tree, we "visit" each of the nodes in the tree once.

There are actually three steps that we need to perform to traverse a tree:

1. Visit the root node.
2. Visit the entire left subtree.
3. Visit the entire right subtree.

Like nearly all tree algorithms, this is a recursive process. To visit the left and right subtrees, we recurse and then treat each subtree as if it was the whole tree. The base case for the traversal is when the tree we are traversing has no nodes.

There are actually different ways we can traverse the nodes based on when we visit the root node. If we do it first, we will always visit a node before visiting its children. This is called a preorder traversal.

If we instead change the traversal to visit the root node between the left and right subtrees like so:

1. Visit the entire left subtree.
2. Visit the root node.
3. Visit the entire right subtree.

This will visit the nodes in the tree in a different order. It will always visit the nodes to the left of a given node, then the root, then those to the right. This is called an inorder traversal.

Lastly, if we visit the root node last, then we will have a postorder traversal.

Below is the code for doing these traversals in Java:


public static void preorder(Node node) {
if (node != null) {
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
}
}

public static void inorder(Node node) {
if (node != null) {
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
}

public static void postorder(Node node) {
if (node != null) {
postorder(node.left);
postorder(node.right);
System.out.print(node.data + " ");
}
}


Notice that the code is exactly the same in each of these except for the time in which we handle the node we are currently on.

## Binary Search Trees

A binary tree is a specific kind of tree, and a binary search tree is a specific kind of binary tree. Specifically it is a binary tree that obeys the following rules:

• The left subtree of a node N contains only nodes with values less than that of the node N.
• The right subtree of a node N contains only nodes with values greater than that of the node N.
• No two nodes can have the same value.

Below is an example of a binary tree that is also a binary search tree:

The goal of binary search trees is to store data in a way that is amenable to the binary search algorithm. To search a tree for an item, we can start at the root node and compare the value there to the target. If the target is larger, then we know that the target must be in the right subtree and if the target is smaller, we know the target is in the left subtree.

Recall that with binary search we can search a sorted array in $O(\log n)$ time. We can also search a binary search tree in $O(\log n)$ time. However the advantage of a binary search tree is that we can also insert quickly.

## Inserting

If we are to insert a new value 60 into the tree above, where should it go?

We can't violate the rule that the nodes in the left subtree must be less than that of the node. So 60 must be inserted to the right side of the root node 56. Then we look at the root of the right subtree, 76. 60 is less than 76 so it must go in the left subtree of the 76 node. Then we get to the node 63, and 60 is less than that node, so it must go in the left subtree. There is no left subtree of this node, so we create one to store our new node and are done.

This is what the tree will look like after inserting 60:

Given a binary search tree and a new item to insert into it, there is always exactly one place that we can put it.

The algorithm to insert into a binary search tree looks like this:

1. To insert a value at a given node:
1. If the node is null, create a new node here with the value.
2. Otherwise, if the data at this node is less than the new value:
Insert the value in the right subtree.
3. Otherwise, if the data at this node is greater than the new value:
Insert the value in the left subtree.

Here is the code for doing the insertion in Java:


// recursive function to insert at a particular node
private Node insertAt(Type value, Node node) {
// if this part of the tree is empty, return a new node
if (node == null) {
return new Node(value);
}

// otherwise, insert into the appropriate side recursively
if (node.data.compareTo(value) < 0) {
node.right = insertAt(value, node.right);
} else {
node.left = insertAt(value, node.left);
}

return node;
}

// insert a number calls recursive function to insert at the root
public void insert(Type value) {
root = insertAt(value, root);
}


Like other recursive methods, there are actually two methods here. The first one does the bulk of the work, but needs an extra parameter, indicating where in the tree we are looking. The second just supplies the starting value of the root node.

Also notice that the method is returning the node it's creating. The reason for that is that we need to assign the node into the reference that points to it (which is either root or one of the left/right references).

## Searching

Searching a binary search tree uses the same basic idea behind regular binary search and is similar to the insertion algorithm above. At each step of the search, we consider a node and there are four possibilities. Either the node is null, in which case the item doesn't exist in the tree. Or the node has the data we want in which case we have found what we were searching for. Or the node has a value that is less than the item we are searching for, in which case we must search the right subtree. Or the node has a value that is more than the item we are searching for, in which case we must search the left subtree. We will start at the root and recursively work our way down.

This can be summarized in the following algorithm:

1. To search for a target at a given node:
2. If the node has the data, return it.
3. If the node's value is less than target, search the right subtree.
4. Otherwise, search left subtree.

Here is this algorithm expressed in Java code:


// recursive function to search starting at a particular node it
private Node searchAt(Type target, Node node) {
if (node == null) {
return null;
} else if (node.data.equals(target)) {
return node;
} else if (node.data.compareTo(target) < 0) {
return searchAt(target, node.right);
} else {
return searchAt(target, node.left);
}
}

// search for a value starting at the root
public Type search(Type target) {
Node node = searchAt(target, root);
if (node == null) {
return null;
} else {
return node.data;
}
}


Here the non-recursive helper method also takes the Node that was returned and pulls the data out of it.

## Removal

Removing a node from a binary search tree is a bit more complicated than inserting or searching one.

If we want to remove a particular element from a tree, we must first search for the node with that value (using the searching algorithm described above). However, once we find the data we want to remove, there are three different cases.

1. The node is a leaf:

In this case, we can simply remove the node, and set the link to it to null.

2. The node has one child:

In this case, we must set the parents pointer equal to the node's only child.

3. The node has two children:

This is the most complicated case.

If we just remove the node, then the tree will be split into two pieces so it will no longer be a tree. We will need to find a new root of the subtree that we are deleting. We also must obey the rules governing binary search trees, so we can't use any node for the new node.

There are only two nodes that we can use for the new root, either the smallest value on the right, or the largest value on the left.

We can then swap the data at those two nodes, as shown in the center picture above. Then there will be a duplicate node, so we must then delete that one (which we can do recursively).

The algorithm to remove a node from a binary search tree is as follows:

1. If the node has no children, return null to its parent.
2. If the node has only a left child, return node.left to its parent, bypassing it.
3. If the node has only a right child, return node.right to its parent, bypassing it.
4. If the node has two children:
1. Find the node with the least value in the node.right subtree.
2. Swap the data at the least node with the one we want to remove.
3. Remove the least node.

To find the smallest node on a subtree we can use the following algorithm:

1. If the node at the root of the subtree has no left child, return the data at the root.
2. Otherwise recursively find the smallest node on the left subtree.

BinarySearchTree.java contains all of the necessary code dealing with binary search trees so far, including inserting, searching, and now removing.

## Balance

Note that there are multiple ways to build a binary search tree storing the same data depending on the order in which the nodes are inserted. What happens if we insert values in a sorted order?

What is produced from this is basically a singly-linked list. The reason for this is that when the nodes are inserted in order, each successive value is greater than any previous ones, so the insertion can only take the right branch. So the left branches are never used and we end up with a line of nodes:

This is called a degenerate tree.

The ideal case is that the tree is balanced which means that, for each node, no subtree is more than 1 node deeper than the other subtree.

The efficiency of the binary search tree depends on it being reasonably well balanced.

## Balancing a Binary Search Tree

There are a few ways to balance a binary search tree. Perhaps the simplest way is to take the data out of it and store it, in sorted order, in a temporary array. Then, take the data in the array and re-insert it into the binary search tree in such a way that the tree will be balanced.

To take the data out, we can simply do an inorder traversal, and store the data in an array as we visit each node. Then we can remove each node from the tree using the remove function above repeatedly.

Then all that remains is to rebuild the tree from the array. Given a sorted array of items, in what order should we insert the items to achieve a balanced tree?

Let's begin with the first item. The first item that is added will become the root of the tree. Which item do we want as the root? Ideally it would be the middle value of the data. That way there will be an equal number of items in the left subtree as there are in the right subtree:

After adding the root, we will have to add the items to the left and those to the right. The first item from the left we add will be the immediate left child of the root. For the same reasons that the root should be the middle item, the left child of the root should be from the middle of the left half of the array. Likewise for the right.

We will add the middle item, then recursively add the left and right halves of the array using the same procedure. This balancing algorithm is given below:

1. Create an array to hold the elements.
2. Fill the array using an in-order traversal.
3. Remove all of the nodes from the tree.
4. Insert the entire array items using the recursive algorithm below.

This recursive algorithm will insert the array items:

1. If there are elements in the array:
1. Calculate the middle of the array.
2. Insert the middle item.
3. Recursively insert the left half.
4. Recursively insert the right half.

Balance.java adds this balancing algorithm into the code we have so far.

## Analysis

The two main binary search tree operations, insertion and searching are both $O(\log n)$ when the tree is balanced. This is due to the fact that with a perfectly balanced tree, the height is limited to the log base 2 of n and the height determines the most times we could recurse.

In the worst case, however, the tree is degenerate so the height will be equal to n. This would make insertion and searching both take $O(n)$ time.

If we balance a binary search tree, we ensure that it can be used in $O(\log n)$ time.

Arrays can also be searched in $O(\log n)$ time using binary search. However, inserting into a binary search tree is faster than inserting into an array - especially since the array must remain sorted for binary search to work.