Binary Search Tree Data Structure

Binary Search Tree Data Structure

Binary Search Tree

A Binary Search Tree (BST) is a data structure that stores a collection of elements in a way that allows for efficient insertion, deletion, and search operations. The key property of BST is that each node in the tree can have at max two child nodes, left and right child nodes.

Additionally, for each node in the tree, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value.

Binary Search Tree Data Structure

This property allows for efficient searching of elements in the tree, as we can discard entire subtrees based on the values of their root nodes. Specifically, to search for a value in a BST, we compare it to the value of the root node. If the value is less than the root, we recurse on the left subtree, and if it is greater than the root, we recurse on the right subtree. If the value is equal to the root, we have found the element.

Searching in Binary Search Tree

Searching for a value in a BST is similar to traversing the tree, but with an additional condition that helps to determine which subtree to search next. If the value is less than the root, we can say for sure that the value is not in the right subtree, we need to only search in the left subtree and if the value is more than the root, we can say for sure that the value is not in the left subtree and we need to only search in the right subtree.

Here is a step by step guide for searching for a value in a Binary Search Tree

  1. Start at the root node of the BST.
  2. Compare the value we want to search for to the value at the current node.
  3. If the value is less than the current node's value, move to the left subtree.
  4. If the value is greater than the current node's value, move to the right subtree.
  5. If the value is equal to the current node's value, we have found the node we were searching for. Return the node.
  6. Repeat steps 2-5 until we either find the node we were searching for or reach a null pointer.
  7. If we reach a null pointer without finding the node, the value is not in the tree. Return null.
Let's walk through an example to see how this works. Suppose we want to search for the value 7 in the following BST 
      10
     /  \
    5    15
   / \     \
  2   7     20
Here are the steps we would follow:
  1. Start at the root node (value 10).
  2. Compare the value 7 to the value 10.
  3. Since 7 is less than 10, move to the left subtree.
  4. Compare the value 7 to the value 5.
  5. Since 7 is equal to 7, we have found the node we were searching for. Return the node.
  6. We can stop here since we have found the node.
  7. The returned node would contain the value 7.
As you can see, searching for a value in a Binary Search Tree is a simple process of comparing the value to search with the values at each node and moving left or right depending on the result of the comparison.

Inserting into a Binary Search Tree

Inserting a value in the correct position is similar to searching because we try to maintain the BST rule that all nodes of left subtree is lesser than root and all nodes of right subtree is larger than root.

Here is a step by step guide for inserting a value into a Binary Search Tree

  1. Start at the root node of the BST.
  2. Compare the value we want to insert to the value at the current node.
  3. If the value is less than the current node's value, move to the left subtree.
  4. If the value is greater than the current node's value, move to the right subtree.
  5. Repeat steps 2-4 until we reach a null pointer.
  6. Create a new node with the value.
  7. Insert the new node at the location where we stopped at the null pointer.
Let's walk through an example to see how this works. Suppose we have the following BST 
      10
     /  \
    5    15
   / \     \
  2   7     20
We want to insert the value 12 into the tree. Here are the steps we would follow:
  1. Start at the root node (value 10).
  2. Compare the value 12 to the value 10.
  3. Since 12 is greater than 10, move to the right subtree.
  4. Compare the value 12 to the value 15.
  5. Since 12 is less than 15, move to the left subtree.
  6. Compare the value 12 to the value 20.
  7. Since we have reached a null pointer, create a new node with the value 12.
  8. Insert the new node at the location where we stopped at the null pointer.
The resulting BST would look like this 
      10
     /  \
    5    15
   / \   / \
  2   7 12  20
As you can see, the new value 12 was inserted as a child of the node with value 15, since 12 is greater than 10 but less than 15.

Deleting a node from a Binary Search Tree

Here is a step by step guide for deleting a node from a Binary Search Tree

  1. If the tree is empty, return null.
  2. Start at the root node of the BST.
  3. Compare the value we want to delete to the value at the current node.
  4. If the value is less than the current node's value, move to the left subtree.
  5. If the value is greater than the current node's value, move to the right subtree.
  6. If the value is equal to the current node's value, we have found the node we want to delete. There are three cases to consider:
    • If the node has no children, simply delete the node and set the parent's child pointer to null.
    • If the node has one child, set the parent's child pointer to the node's child.
    • If the node has two children, we need to find the node's successor (i.e., the node with the smallest value in the right subtree), replace the node's value with the successor's value, and delete the successor node. This maintains the BST property while removing the node we want to delete.
  7. Repeat steps 3-6 until we either find the node we want to delete or reach a null pointer.
Let's walk through an example to see how this works. Suppose we want to delete the node with value 5 from the following BST 
      10
     /  \
    5    15
   / \     \
  2   7     20
Here are the steps we would follow:
  1. Start at the root node (value 10).
  2. Compare the value 5 to the value 10.
  3. Since 5 is less than 10, move to the left subtree.
  4. Compare the value 5 to the value 5.
  5. We have found the node we want to delete. Since the node has two children, we need to find the node's successor. The successor of a node is the node with the smallest value in the node's right subtree.
  6. In this case, the successor of the node with value 5 is the node with value 7. We replace the value of the node with value 5 with the value of the node with value 7, and then delete the node with value 7. This maintains the BST property while removing the node we want to delete.
The resulting BST after deletion would look like this 
      10
     /  \
    7    15
   /       \
  2         20
As you can see, the node with value 5 has been removed from the tree.

Time Complexity of Binary Search Tree Operations

BSF Operations Best Case Average Case Worst Case
Search O(1) O(log n) O(n)
Insert O(1) O(log n) O(n)
Delete O(1) O(log n) O(n)
Find Minimum O(1) O(log n) O(n)
Find Maximum O(1) O(log n) O(n)
Successor O(1) O(log n) O(n)
Predecessor O(1) O(log n) O(n)

In the table above, n represents the number of nodes in the tree.

  • The best-case time complexity occurs when the node being searched, inserted, or deleted is the root node or is very close to the root node. In this case, the operation takes constant time, O(1).

  • The average-case time complexity occurs when the Binary Search Tree is balanced, and the nodes are distributed evenly across the tree. In this case, the height of the tree is O(log n), and the average-case time complexity of each operation is also O(log n).

  • The worst-case time complexity occurs when the Binary Search Tree is unbalanced, and the nodes are arranged in a linked list fashion. In this case, the height of the tree is O(n), and the worst-case time complexity of each operation is also O(n).

Advantages and Limitations of Binary Search Tree Data Structure

Advantages
  • Efficient Searching : BSTs provide efficient searching with logarithmic time complexity, making them suitable for applications where quick search operations are essential.

  • Ordered Structure : The ordered structure of a BST facilitates range queries and operations that require ordered data.

  • Dynamic Operations : BSTs support dynamic operations such as insertion and deletion, making them adaptable to changing datasets.
Limitations
  • Dependence on Ordering : The efficiency of BST operations depends on the ordering of elements. An already sorted or poorly balanced tree can result in skewed structures, impacting performance.

  • No Global Balancing : Unlike balanced trees (e.g., AVL or Red-Black trees), BSTs do not have a global balancing mechanism. Therefore, the overall balance may not be guaranteed.

  • Performance Sensitivity : The performance of BSTs can degrade in the worst-case scenario, especially if they become unbalanced due to sequential or sorted input.

Binary Search Tree Implementation Program

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

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

struct Node* deleteNode(struct Node* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        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;
        }
        struct Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

struct Node* search(struct Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return search(root->left, data);
    } else {
        return search(root->right, data);
    }
}

void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    struct Node* root = NULL;

    // Insert nodes into the tree
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 2);
    root = insert(root, 7);
    root = insert(root, 20);

    printf("Inorder traversal of the BST:\n");
    inorderTraversal(root);
    printf("\n");

    // Search for a node in the tree
    int searchValue = 7;
    struct Node* searchedNode = search(root, searchValue);
    if (searchedNode != NULL) {
        printf("%d was found in the BST.\n", searchValue);
    } else {
        printf("%d was not found in the BST.\n", searchValue);
    }

    // Delete a node from the tree
    int deleteValue = 5;
    root = deleteNode(root, deleteValue);
    printf("Inorder traversal of the BST after deleting %d:\n", deleteValue);
    inorderTraversal(root);
    printf("\n");

    return 0;
}
Output 
Inorder traversal of the BST:
2 5 7 10 15 20 
7 was found in the BST.
Inorder traversal of the BST after deleting 5:
2 7 10 15 20

Conclusion

Binary Search Trees are powerful and widely used data structures, especially in scenarios where efficient searching and dynamic operations are critical. Understanding the principles of BSTs, including their operations, best practices, and advantages and limitations, is essential for utilizing them effectively in different applications. By applying best practices and considering the nature of the data, developers can harness the benefits of BSTs while mitigating potential limitations. Overall, Binary Search Trees remain a fundamental tool in the realm of data structures, contributing to the efficiency and flexibility of algorithmic solutions.

Previous
Binary Tree
Next
Graph
Posted by
Labels:
Location: Seattle, WA, USA