Binary Search Trees

A Binary Search Tree is a binary tree that additionally satisfies the binary search property. This type of tree is similar to how a binary search works on an array. The number of elements to compare decreases every time the search progresses.

Binary Search Property

The binary search property states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.

We can derive 4 points from this:

1. The left subtree of a node will contain only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each, in turn, would be a binary tree.
4. There must be no duplicate nodes in the tree.

Operations in a Binary Search Tree

Searching

To search for a key in the tree, we follow the step similar to a binary search:

Steps

1. Compare the key to be searched with the root’s key.
2. If the key is present at the root, then we have found the key.
3. If the key is lesser than the root’s value, we return the left subtree of the node.
4. If the key is greater than the root’s value, we return the right subtree of the node.
5. The search is continued recursively until the element is found, or all nodes are exhausted.

Insertion

To insert for a key in the tree, we follow the binary search property and insert accordingly:

Steps

1. Compare the key to be searched with the root’s key.
2. If the key is lesser than the root’s value, we return the left subtree of the node.
3. If the key is greater than the root’s value, we return the right subtree of the node.
4. This process is continued until we hit a leaf node. The new node is inserted to this location as a new node.

struct node* insertNode(struct node* root, int data)
{
    if (root == NULL) return createNode(data);

    if (data < root->data)
        root->left  = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);

    return root;
}

Deletion

Deletion in a binary search tree is more complex than insertion.

It is mandatory to maintain the in-order sequence of the nodes while deletion. There are three possible cases to consider:

1. Deleting a node with no children

The node is simply removed from the tree. The in-order sequence is already maintained in this case.

2. Deleting a node with one child

The node is removed and replaced with its child. In the implementation, we copy the child node to the node to be deleted and then delete the child node.

3. Deleting a node with two children

First, we find the in-order successor of the node. Then the contents of this in-order successor are copied to the node to be deleted. Finally, the in-order successor is deleted.

/* function to find the minimum value of a node in a tree */
struct node * minValueNode(struct node* node) 
{ 
    struct node* current = node; 
  
    /* loop down to find the leftmost leaf */
    while (current && current->left != NULL) 
        current = current->left; 
  
    return current; 
} 
  
/* function to delete a key from a binary search tree */
struct node* deleteNode(struct node* root, int key) 
{ 
    // base case 
    if (root == NULL) return root; 
  
    // If the key to be deleted is smaller than the root's key, 
    // then it lies in left subtree 
    if (key < root->key) 
        root->left = deleteNode(root->left, key); 
  
    // If the key to be deleted is greater than the root's key, 
    // then it lies in right subtree 
    else if (key > root->key) 
        root->right = deleteNode(root->right, key); 
  
    // if key is same as root's key, then This is the node 
    // to be deleted 
    else
    { 
        // node with only one child or no child 
        if (root->left == NULL) 
        { 
            struct node *temp = root->right; 
            free(root); 
            return temp; 
        } 
        else if (root->right == NULL) 
        { 
            struct node *temp = root->left; 
            free(root); 
            return temp; 
        } 
  
        // node with two children: Get the inorder successor (smallest 
        // in the right subtree) 
        struct node* temp = minValueNode(root->right); 
  
        // Copy the inorder successor's content to this node 
        root->key = temp->key; 
  
        // Delete the inorder successor 
        root->right = deleteNode(root->right, temp->key); 
    } 
    return root; 
} 

Videos

Shorter

• Data structures: Binary Search Tree | mycodeschool
• Binary search tree – Implementation in C/C++ | mycodeschool
• Delete a node from Binary Search Tree | mycodeschool

Longer

• Binary Search Trees, BST Sort | MIT OpenCourseware