Binary Search Trees

Binary Search Trees

A binary search tree (BST) is a type of binary tree that maintains a specific order. In a BST, for every node, the left subtree contains only nodes with values less than the node's value, and the right subtree contains only nodes with values greater than the node's value. This property allows for efficient searching, insertion, and deletion of nodes.

Properties of Binary Search Trees

Binary search trees have several important properties:

• Each node has at most two children.
• The left child contains a value less than its parent node.
• The right child contains a value greater than its parent node.
• Both left and right subtrees must also be binary search trees.

Structure of a Binary Search Tree

A binary search tree can be represented using a class in C++. Each node of the tree typically contains three components:

1. The value of the node.
2. A pointer/reference to the left child.
3. A pointer/reference to the right child.

Here is an example of how to define a node in C++:

class Node {
public:
    int value;
    Node* left;
    Node* right;
    Node(int val) : value(val), left(nullptr), right(nullptr) {}
};

Creating a Binary Search Tree

To create a binary search tree, you start with an empty tree and insert values one by one. The first value becomes the root node. Each subsequent value is compared to the current node. If it is less, you move to the left child; if it is greater, you move to the right child. You repeat this process until you find an empty spot for the new value.

Here is an example of inserting values into a binary search tree:

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

Example of Insertion

Consider the following sequence of values: 50, 30, 70, 20, 40, 60, 80. We will insert these values into a binary search tree.

1. Insert 50: The tree is empty, so 50 becomes the root.
2. Insert 30: 30 is less than 50, so it goes to the left of 50.
3. Insert 70: 70 is greater than 50, so it goes to the right of 50.
4. Insert 20: 20 is less than 50 and less than 30, so it goes to the left of 30.
5. Insert 40: 40 is less than 50 but greater than 30, so it goes to the right of 30.
6. Insert 60: 60 is greater than 50 but less than 70, so it goes to the left of 70.
7. Insert 80: 80 is greater than 50 and greater than 70, so it goes to the right of 70.

The resulting binary search tree looks like this:

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

Searching in a Binary Search Tree

Searching for a value in a binary search tree follows a similar approach to insertion. Start at the root and compare the target value with the value of the current node. If they are equal, you have found the value. If the target value is less, move to the left child; if greater, move to the right child. Repeat this process until you find the value or reach a null pointer.

Here is a function to search for a value in a binary search tree:

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

Example of Searching

Using the previous binary search tree, if you want to search for the value 60:

1. Start at the root (50). 60 is greater than 50, so move to the right child (70).
2. At node 70, 60 is less than 70, so move to the left child (60).
3. At node 60, you find the value. The search is successful.

Deleting a Node from a Binary Search Tree

Deleting a node from a binary search tree is more complex than inserting or searching. There are three cases to consider:

1. The node to be deleted is a leaf node (has no children).
2. The node to be deleted has one child.
3. The node to be deleted has two children.

Case 1: Deleting a Leaf Node

If the node is a leaf, simply remove it from the tree by setting its parent's pointer to null.

Case 2: Deleting a Node with One Child

If the node has one child, remove the node and link its parent directly to its child.

Case 3: Deleting a Node with Two Children

If the node has two children, you need to find the in-order successor (the smallest value in the right subtree) or the in-order predecessor (the largest value in the left subtree) to replace the deleted node's value. After replacing the value, delete the successor or predecessor node.

Here is a function to delete a node from a binary search tree:

Node* deleteNode(Node* root, int value) {
    if (root == nullptr) {
        return root;
    }
    if (value < root->value) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->value) {
        root->right = deleteNode(root->right, value);
    } else {
        // Node with only one child or no child
        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 with two children
        Node* temp = minValueNode(root->right);
        root->value = temp->value;
        root->right = deleteNode(root->right, temp->value);
    }
    return root;
}

Finding the Minimum Value Node

To find the minimum value node in a binary search tree, you keep moving to the left child until you reach a node with no left child. Here is a function to do this:

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}

Tree Traversal Techniques

Tree traversal techniques are methods for visiting all the nodes in a binary search tree. The most common techniques are:

• In-order traversal: Visit the left subtree, the root, and then the right subtree. This results in values being visited in ascending order.
• Pre-order traversal: Visit the root, then the left subtree, and finally the right subtree. This is useful for creating a copy of the tree.
• Post-order traversal: Visit the left subtree, the right subtree, and then the root. This is useful for deleting the tree.

Here is an example of in-order traversal in C++:

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

Summary

• A binary search tree is a binary tree with specific ordering properties.
• Insertion, searching, and deletion are key operations in a binary search tree.
• Tree traversal techniques include in-order, pre-order, and post-order.

Check your understanding

1. What are the properties of a binary search tree?
2. Describe the process of inserting a value into a binary search tree.
3. Explain how to delete a node with two children from a binary search tree.
4. What is the difference between in-order, pre-order, and post-order traversal?