Binary Search Tree in Data Structure

A Binary Search Tree is a Binary Tree that contains the nodes sorted in a particular order. The ordering helps to perform the search, insertion, and deletion operations faster than the linear data structures.

1. Introduction

The Binary Search Tree is required for applications that perform frequent search, insert, and delete operations with sorted data. However, this is not efficient in the worst case when the tree is not balanced. See the balanced version of Binary Search Trees such as AVL Tree and Red-Black Tree to address this issue.

Representation

// Tree node representation
struct Node
{
    int data;    // Actual data
    Node* left;  // Pointer to left child
    Node* right; // Pointer to right child

    // Node constructor
    Node(int d) : data(d), left(NULL), right(NULL)
    {}
};

Node* root;

Applications

• Application with the sorted stream of data and requires a faster search/insert/delete operations in O(log n) time. For example, search all orders that are below the particular cost (ordering the elements by cost). (Note: A Hash Table can perform search/insert/delete in O(1) time, but it is not suitable for comparison with orders).
• Implement the double-ended priority queue with GetMin and GetMax in O(log n) time. (Note: A Binary Heap is single-ended and either GetMin or GetMax can be in O(1) time).

2. Insertion on Binary Search Tree

A node is always inserted in the depth of the tree based on the element. So, we need to traverse the tree based on the element value and insert the new node in its position.

Algorithm

1. Start the traversal from the root node to find the data location.
2. If the data element is smaller than the current node, traverse on the left subtree.
3. Otherwise, traverse on the right subtree if the data element is greater.
4. Insert the node when the traversal reached its depth and found the location.

Code

// Insert a new node
Node* BinarySearchTree::insert(Node* p, int data)
{
    if (p == NULL) {
        // Found the location. Insert the node
        return new Node(data);
    } else if (data < p->data) {
        // Insert on left sub tree
        p->left = insert(p->left, data);
    } else {
        // Insert on right sub tree
        p->right = insert(p->right, data);
    }

    return p;
}

Examples

The following diagrams illustrate the insertions for the data 30, 20, 50, 40, 10, and 60.

3. Deletion on Binary Search Tree

Traverse the tree based on the node order to find the data element and delete the node by rearranging the child nodes. In case the target node has two children, this will be replaced by the next smaller element to avoid losing its children.

Algorithm

1. Start the traversal from the root node to find the target node.
2. If the data element is smaller than the current node, traverse on the left subtree.
3. Otherwise, traverse on the right subtree if the data element is greater.
4. If the target is found, delete the node without losing the reference to its children.
   • No child for the target node: Delete the node and return NULL to unlink from the parent.
   • Only has the right child: Delete the node and link the left child to its parent directly.
   • Only has the left child: Delete the node and link the right child to its parent directly.
   • Both left and right children: Find the next smaller data element (in-order successor) node, and replace the target node with its in-order successor.
5. Otherwise, return NULL if the traversal is completed without finding the element.

Code

// Delete the node by the given data
Node* BinarySearchTree::remove(Node* p, int data)
{
    if (p == NULL) {
        // Reached the depth and the node not found
        return NULL;
    }

    if (data < p->data) {
        // Search on the left subtree for smaller elements.
        p->left = remove(p->left, data);

    } else if (data > p->data) {
        // Search on the right subtree for greater elements.
        p->right = remove(p->right, data);

    } else {
        // Found the target node
        // Node has either no child or one child
        if (p->left == NULL) {
            Node* right = p->right;
            delete p;
            return right;
        } else if (p->right == NULL) {
            Node* left = p->left;
            delete p;
            return left;
        }

        // Node has both left and right child.
        // Find the smallest node on its right subtree (inorder successor)
        Node* min;
        for (min = p->right; min->left != NULL; min = min->left)
            ;

        // Replace the target node's data with the smallest node
        p->data = min->data;
        p->right = remove(p->right, min->data);
    }

    return p;
}

Examples

The following diagrams illustrate the deletions on Binary Search Tree

1. Delete the node (60) which has no children

2. Delete the node (20) which has one child

3. Delete node (40) which has two children

4. Searching an Element

Search the data element by traversing the tree from the root node. Proceed the search either on its left or right subtree based on the node order.

Algorithm

1. Start the traversal from the root node to find the target node.
2. If the data matches the current node, return the node.
3. Traverse on the left subtree if the data element is smaller than the current node,
4. Traverse on the right subtree if the data element is greater.
5. Return NULL if the traversal is completed without finding the element.

Code

// Search the node by the given data
Node* BinarySearchTree::search(Node* p, int data)
{
    if (p == NULL) {
        // Reached the depth and the node not found
        return NULL;
    }

    // Check if the current node matches the data and return the node if true.
    if (data == p->data) {
        return p;
    } else if (data < p->data) {
        // Search on the left sub tree and return the node if found.
        return search(p->left, data);
    } else {
        // Search on the right sub tree and return the node if found.
        return search(p->right, data);
    }
}

5. Traversals

See Traversals on Binary Tree that are applicable for Binary Search Tree.

6. Implementation of Binary Search Tree in C++

/**
 * C++ example to demonstrate the Binary Search Tree
 */
#include <iostream>
#include <queue>
using namespace std;

// Tree node representation
struct Node
{
    int data;    // Actual data
    Node* left;  // Pointer to left child
    Node* right; // Pointer to right child

    // Node constructor
    Node(int d) : data(d), left(NULL), right(NULL)
    {}
};

/**
 * Binary Search Tree implementation
 */
class BinarySearchTree
{
    // The root node
    Node* root;

public:
    // Constructor
    BinarySearchTree() : root(NULL)
    {}

    // Insert a new node
    void insert(int data) {
        root = insert(root, data);
    }

    // Delete the node by the given data
    void remove(int data) {
        root = remove(root, data);
    }

    // Search the node by the given data
    Node* search(int data) {
        return search(root, data);
    }
    
    // Preorder traversal
    void preorder() {
        preorder(root);
    }

    // Postorder traversal
    void postorder() {
        postorder(root);
    }

    // Inorder traversal
    void inorder() {
        inorder(root);
    }

    // Levelorder traversal
    void levelorder() {
        levelorder(root);
    }

private:
    // Private methods that works recursively to perform the operations
    Node* insert(Node* p, int data);
    Node* remove(Node* p, int data);
    Node* search(Node* p, int data);
    void preorder(Node* p);
    void postorder(Node* p);
    void inorder(Node* p);
    void levelorder(Node* p);
};

// Insert a new node
Node* BinarySearchTree::insert(Node* p, int data)
{
    if (p == NULL) {
        // Found the location. Insert the node
        return new Node(data);
    } else if (data < p->data) {
        // Insert on left sub tree
        p->left = insert(p->left, data);
    } else {
        // Insert on right sub tree
        p->right = insert(p->right, data);
    }

    return p;
}

// Delete the node by the given data
Node* BinarySearchTree::remove(Node* p, int data)
{
    if (p == NULL) {
        // Reached the depth and the node not found
        return NULL;
    }

    if (data < p->data) {
        // Search on the left subtree for smaller elements.
        p->left = remove(p->left, data);

    } else if (data > p->data) {
        // Search on the right subtree for greater elements.
        p->right = remove(p->right, data);

    } else {
        // Found the target node
        // Node has either no child or one child
        if (p->left == NULL) {
            Node* right = p->right;
            delete p;
            return right;
        } else if (p->right == NULL) {
            Node* left = p->left;
            delete p;
            return left;
        }

        // Node has both left and right child.
        // Find the smallest node on its right subtree (inorder successor)
        Node* min;
        for (min = p->right; min->left != NULL; min = min->left)
            ;

        // Replace the target node's data with the smallest node
        p->data = min->data;
        p->right = remove(p->right, min->data);
    }

    return p;
}

// Search the node by the given data
Node* BinarySearchTree::search(Node* p, int data)
{
    if (p == NULL) {
        // Reached the depth and the node not found
        return NULL;
    }

    // Check if the current node matches the data and return the node if true.
    if (data == p->data) {
        return p;
    } else if (data < p->data) {
        // Search on the left sub tree and return the node if found.
        return search(p->left, data);
    } else {
        // Search on the right sub tree and return the node if found.
        return search(p->right, data);
    }
}

// Traverse the tree in preorder (parent, left, right)
void BinarySearchTree::preorder(Node* p)
{
    if (p != NULL) {
        cout << p->data << endl;
        preorder(p->left);
        preorder(p->right);
    }
}

// Traverse the tree in postorder (left, right, parent)
void BinarySearchTree::postorder(Node* p)
{
    if (p != NULL) {
        postorder(p->left);
        postorder(p->right);
        cout << p->data << endl;
    }
}

// Traverse the tree inorder (left, parent, right)
void BinarySearchTree::inorder(Node* p)
{
    if (p != NULL) {
        inorder(p->left);
        cout << p->data << endl;
        inorder(p->right);
    }
}

// Traverse the tree in level order (breadth first)
void BinarySearchTree::levelorder(Node* p)
{
    if (p == NULL) {
        return;
    }

    // Start the traversal from root node
    std::queue<Node*> q;
    q.push(root);

    while (! q.empty()) {
        Node* p = q.front();
        q.pop();

        // Visit the current node
        cout << p->data << endl;

        // Enqueue the left and right child to process in order.
        if (p->left != NULL) {
            q.push(p->left);
        }
        if (p->right != NULL) {
            q.push(p->right);
        }
    }
}

int main()
{
    /** Create a binary search tree and insert data
     *           30
     *         /    \
     *        20    50
     *       /     /  \
     *      10   40    60
     */
    BinarySearchTree tree;
    tree.insert(40);
    tree.insert(20);
    tree.insert(50);
    tree.insert(30);
    tree.insert(10);

    // Search
    Node* p = tree.search(30);
    cout << "Search(30) located node: " << p->data << endl;

    // Traversals
    cout << "Binary Tree inorder traversal" << endl;
    tree.inorder();
    cout << "Binary Tree preorder traversal" << endl;
    tree.preorder();
    cout << "Binary Tree postorder traversal" << endl;
    tree.postorder();
    cout << "Binary Tree level order traversal" << endl;
    tree.levelorder();

    // Delete data
    tree.remove(20);
    tree.remove(10);
    cout << "Binary Tree level inorder traversal after removing 20 and 10" << endl;
    tree.inorder();
}

Output

Search(30) located node: 30
Binary Tree inorder traversal
10
20
30
40
50
Binary Tree preorder traversal
40
20
10
30
50
Binary Tree postorder traversal
10
30
20
50
40
Binary Tree level order traversal
40
20
50
10
30
Binary Tree level inorder traversal after removing 20 and 10
30
40
50

7. References

• Binary Search Tree Wiki