Binary Search Trees

1 Introduction

We consider a particular kind of a binary tree called a Binary Search Tree (BST). The basic idea
behind this data structure is to have such a storing repository that provides the efficient way of
data sorting, searching and retrieving.

A BST is a binary tree where nodes are

ordered in the following way:

 each node contains one key (also

known as data)
 the keys in the left subtree are less
then the key in its parent node, in short
L < P;
 the keys in the right subtree are greater
the key in its parent node, in short P <
R;
 duplicate keys are not allowed.

In the following tree all nodes in the left

subtree of 10 have keys < 10 while all nodes
in the right subtree > 10. Because both the left
and right subtrees of a BST are again search
trees; the above definition is recursively
applied to all internal nodes:

2 Implementation
2.1 Binary search tree node

We implement a binary search tree using a private inner class BSTNode. In order to support the
binary search tree property, we require that data stored in each node is Comparable:

private class Node<AnyType>

{
private AnyType data;
private Node<AnyType> left, right;

public Node(AnyType data)

{
left = right = null;
this.data = data;
}
}

1
2.2 Binary search tree

public class BST <AnyType extends Comparable<AnyType>>

{
private Node<T> root;
private Comparator<T> comparator;

public BST()
{
root = null;
comparator = null;
}

public BST(Comparator<T> comp)

{
root = null;
comparator = comp;
}

private int compare(T x, T y)

{
if(comparator == null) return x.compareTo(y);
else
return comparator.compare(x,y);
}
}

3 Insertion

The insertion procedure is quite similar to searching. We start at the root and recursively go down
the tree searching for a location in a BST to insert a new node. If the element to be inserted is
already in the tree, we are done (we do not insert duplicates). The new node will always replace a
NULL reference.

2
Exercise. Given a sequence of numbers:

11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31

Draw a binary search tree by inserting the above numbers from left to right.

3.1 Insertion Operation in BST

In binary search tree, new node is always inserted as a leaf node. The insertion operation is
performed as follows:

 Step 1: Create a newNode with given value and set its left and right to NULL.
 Step 2: Check whether tree is Empty.
 Step 3: If the tree is Empty, then set root to newNode.
 Step 4: If the tree is Not Empty, then check whether value of newNode is smaller or
larger than the node (here it is root node).
 Step 5: If newNode is smaller than to the node, then move to its left child. If newNode is
larger than the node, then move to its right child.
 Step 6: Repeat the above step until we reach to a leaf node (i.e., reach to NULL).
 Step 7: After reaching a leaf node, then insert the newNode as left child if newNode is
smaller to that leaf else insert it as right child.

public void insert(T data)

{
root = insert(root, data);
}
private Node<T> insert(Node<T> p, T toInsert)
{
if (p == null)
return new Node<T>(toInsert);

if (compare(toInsert, p.data) == 0)
return p;

3
 if (compare(toInsert, p.data) < 0)
p.left = insert(p.left, toInsert);
else
p.right = insert(p.right, toInsert);

return p;
}

4 Searching
Searching in a BST always starts at the root. We compare a data stored at the root with the key we
are searching for (let us call it as toSearch). If the node does not contain the key we proceed either
to the left or right child depending upon comparison. If the result of comparison is negative we go
to the left child, otherwise - to the right child. The recursive structure of a BST yields a recursive
algorithm.

Searching in a BST has O(h) worst-case runtime complexity, where h is the height of the tree.
Since s binary search tree with n nodes has a minimum of O(log n) levels, it takes at least O(log
n) comparisons to find a particular node. Unfortunately, a binary search tree can degenerate to a
linked list, reducing the search time to O(n).

4.1 Search Operation in BST

The search operation is performed as follows:

 Step 1: Read the search element from the user

 Step 2: Compare, the search element with the value of root node in the tree.
 Step 3: If both are matching, then display "Given node found!!!" and terminate the
function
 Step 4: If both are not matching, then check whether search element is smaller or larger
than that node value.
 Step 5: If search element is smaller, then continue the search process in left subtree.
 Step 6: If search element is larger, then continue the search process in right subtree.
 Step 7: Repeat the same until we found exact element or we completed with a leaf node
 Step 8: If we reach to the node with search value, then return true and terminate the
function.
 Step 9: If we reach to a leaf node and it is also not matching, then return false and
terminate the function.

public boolean search(T toSearch)

{
return search(root, toSearch);
}
private boolean search(Node<T> p, T toSearch)
{
if (p == null)
return false;
else
if (compare(toSearch, p.data) == 0)

4
 return true;
else
if (compare(toSearch, p.data) < 0)
return search(p.left, toSearch);
else
return search(p.right, toSearch);
}

5 Deletion

Deletion is somewhat trickier than insertion. There are several cases to consider. A node to be
deleted (let us call it as toDelete)

 is not in a tree;
 is a leaf;
 has only one child;
 has two children.

If toDelete is not in the tree, there is nothing to delete. If toDelete node has only one child the
procedure of deletion is identical to deleting a node from a linked list - we just bypass that node
being deleted

Deletion of an internal node with two children is less straightforward. If we delete such a node,
we split a tree into two sub trees and therefore, some children of the internal node won't be
accessible after deletion. In the picture below we delete 8:

5
Deletion strategy is the following: replace the node being deleted with the largest node in the left
subtree and then delete that largest node. By symmetry, the node being deleted can be swapped
with the smallest node is the right subtree.

5.1 Deletion Operation in BST

Deleting a node from Binary search tree has following three cases.

 Case 1: Deleting a Leaf node (A node with no children)

 Case 2: Deleting a node with one child
 Case 3: Deleting a node with two children

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST...

 Step 1: Find the node to be deleted using search operation

 Step 2: Delete the node using free function (If it is a leaf) and terminate the function.

Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...

 Step 1: Find the node to be deleted using search operation

 Step 2: If it has only one child, then create a link between its parent and child nodes.
 Step 3: Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST...

 Step 1: Find the node to be deleted using search operation

6
  Step 2: If it has two children, then find the largest node in its left subtree (OR) the
smallest node in its right subtree.
 Step 3: Swap both deleting node and node which found in above step.
 Step 4: Then, check whether deleting node came to case 1 or case 2 else goto steps 2
 Step 5: If it comes to case 1, then delete using case 1 logic.
 Step 6: If it comes to case 2, then delete using case 2 logic.
 Step 7: Repeat the same process until node is deleted from the tree.

public void delete(T toDelete)

{
root = delete(root, toDelete);
}
private Node<T> delete(Node<T> p, T toDelete)
{
if (p == null) throw new RuntimeException("cannot delete.");
else
if (compare(toDelete, p.data) < 0)
p.left = delete (p.left, toDelete);
else
if (compare(toDelete, p.data) > 0)
p.right = delete (p.right, toDelete);
else
{
if (p.left == null) return p.right;
else
if (p.right == null) return p.left;
else
{
// get data from the rightmost node in the left subtree
p.data = retrieveData(p.left);
// delete the rightmost node in the left subtree
p.left = delete(p.left, p.data) ;
}
}
return p;
}
private T retrieveData(Node<T> p)
{
while (p.right != null) p = p.right;

return p.data;
}

Exercise. Given a sequence of numbers:

11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31

7
Draw a binary search tree by inserting the above numbers from left to right and then show the
two trees that can be the result after the removal of 11.

6 Traversing the Tree

Traversing a tree means visiting each node in a specified order. This process is not as commonly
used as finding, inserting, and deleting nodes.

6.1 Inorder Traversal

An inorder traversal of a binary search tree will cause all the nodes to be visited in ascending
order, based on their key values. A recursive method to traverse the entire tree is called with a
node as an argument. Initially, this node is the root. The method needs to do only three things:

1. Call itself to traverse the node’s left subtree.

2. Visit the node.
3. Call itself to traverse the node’s right subtree.

Remember that visiting a node means doing something to it: displaying it, writing it to a file, or
whatever.

private void inOrder (Node r)

{
if (r != null)
{
inOrder(r.left);
System.out.print(r+" ");
inOrder(r.right);
}
}

8
For these other traversals the same three steps are used as for inOrder, but in a different
sequence. Here’s the sequence for a preOrder() method:

1. Visit the node.

2. Call itself to traverse the node’s left subtree.
3. Call itself to traverse the node’s right subtree.

The third kind of traversal, postOrder, contains the three steps arranged in yet another way:

1. Call itself to traverse the node’s left subtree.

2. Call itself to traverse the node’s right subtree.
3. Visit the node.