Binary Search Trees

[Qingquan-Li]

1. Definition

A Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes.

Example 1: Simple BST

    5
   / \
  3   7
 / \   \
2   4   8

Example 2: BST with Single Child Nodes

    20
   /
  10
    \
     15

Example 3: BST with More Levels

       50
      /  \
    30    70
   / \   /  \
  20 40 60  80

Example 4: Unbalanced BST

5
 \
  10
    \
     15
       \
        20

2. Properties

• Efficient Search: Provides efficient searching, with a time complexity of O(log n) in the average and best cases. However, this can degrade to O(n) in the worst case (when the tree becomes unbalanced).
• Ordered: An in-order traversal of a BST yields the nodes in sorted order.
• Dynamic: BSTs can dynamically grow and shrink, allowing for operations like insertion and deletion of nodes.

Note (Balancing):

A Binary Search Tree, when balanced, offers an efficient means of storing and accessing data in a sorted manner.
To ensure efficient operations, BSTs can be balanced using algorithms like AVL trees or Red-Black trees. This is important to maintain the O(log n) time complexity for search, insert, and delete operations.

3. Applications

BSTs are widely used in various applications where data retrieval and modifications are frequent, such as in database indices, file systems, and associative arrays.

4. Common Operations

Let's go through the common operations on a Binary Search Tree (BST) – Search, Insertion, Deletion, and Traversal – and see how they can be implemented in C++. For simplicity, I'll assume that each node in the BST contains integer values:

Node Structure

First, let's define the structure of a node in the BST:

struct Node {
    int value;
    Node *left;
    Node *right;

    // Node(int val) : value(val), left(nullptr), right(nullptr) {}
    Node(int val) {
        value = val;
        left = nullptr;
        right = nullptr;
    }
};

Search Operation

The search operation looks for a value in the tree.
To find a value, start at the root and compare it against the value to be searched. If the value is less than the current node, go to the left child; if greater, go to the right child. Repeat this process recursively.

bool search(Node* root, int key) {
    if (root == nullptr) {
        return false;
    }
    if (root->value == key) {
        return true;
    }
    if (key < root->value) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

Insertion Operation

Insertion involves finding the right place for a new value and adding it there as a leaf node.
To insert a value, start at the root and compare it against the value to be inserted, following the same logic as the search. The new node is inserted as a leaf.

Node* insert(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }
    if (val < root->value) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

After executing the insertions in main function:

root = insert(root, 5);
insert(root, 3);
insert(root, 7);
insert(root, 2);
insert(root, 4);
insert(root, 6);

The BST will look like this:

     5
   /   \
  3     7
 / \   /
2   4 6

Deletion Operation

Deletion is slightly more complex, as it has three cases: deleting a leaf node, a node with one child, and a node with two children:

• Node to be deleted is a leaf: simply remove the node.
• Node to be deleted has one child: remove the node and replace it with its child.
• Node to be deleted has two children: find the node's in-order successor (the smallest node in its right subtree), copy its value to the node, and delete the in-order successor.

// Helper function to find the node with minimum value
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}

Node* deleteNode(Node* root, int key) {
    if (root == nullptr) {
        return root;
    }
    if (key < root->value) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->value) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        Node* temp = minValueNode(root->right);
        root->value = temp->value;
        root->right = deleteNode(root->right, temp->value);
    }
    return root;
}

Traversal Operations

Traversal can be done in several ways; let's focus on In-order, Pre-order, and Post-order traversals.

In-order Traversal

In-order traversal visits the nodes in ascending order in a Binary Search Tree. It traverses the left subtree, then the current node, and finally the right subtree.

void inorderTraversal(Node* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->value << " ";
        inorderTraversal(root->right);
    }
}

Pre-order Traversal

Pre-order traversal visits the current node before its child nodes. It's used often for copying a tree or for prefix notation expressions.

void preorderTraversal(Node* root) {
    if (root != nullptr) {
        std::cout << root->value << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

Post-order Traversal

Post-order traversal visits the current node after its child nodes. It's useful for deleting trees and for postfix notation expressions.

void postorderTraversal(Node* root) {
    if (root != nullptr) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        std::cout << root->value << " ";
    }
}

Usage Example (main function)

// Main function to demonstrate BST operations
int main() {
    // Creating an empty BST
    Node* root = nullptr;
    // Inserting nodes
    root = insert(root, 5);
    insert(root, 3);
    insert(root, 7);
    insert(root, 2);
    insert(root, 4);
    insert(root, 6);

    // Traversing the BST
    std::cout << "In-order traversal of the BST: ";
    inorderTraversal(root);
    std::cout << std::endl;
    
    std::cout << "Pre-order traversal of the BST: ";
    preorderTraversal(root);
    std::cout << std::endl;
    
    std::cout << "Post-order traversal of the BST: ";
    postorderTraversal(root);
    std::cout << std::endl;

    // Searching for a value
    int key = 4;
    if (search(root, key)) {
        std::cout << "Node with value " << key << " exists in the BST." << std::endl;
    } else {
        std::cout << "Node with value " << key << " does not exist in the BST." << std::endl;
    }

    // Deleting a node
    std::cout << "Deleting node with value 4." << std::endl;
    root = deleteNode(root, 4);
    std::cout << "In-order traversal after deletion: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

Output:

In-order traversal of the BST: 2 3 4 5 6 7 
Pre-order traversal of the BST: 5 3 2 4 7 6 
Post-order traversal of the BST: 2 4 3 6 7 5 
Node with value 4 exists in the BST.
Deleting node with value 4.
In-order traversal after deletion: 2 3 5 6 7