Binary Search Tree

Hi everyone, inside this article we will see the concept about Binary Search Tree.

A Binary Search Tree (BST) is a type of binary tree where each node has a key/value and satisfies the following properties:

1. The key/value of the left child is less than the key/value of its parent node.
2. The key/value of the right child is greater than the key/value of its parent node.
3. The left and right subtrees of a node are also binary search trees.

These properties ensure that the binary search tree is ordered, with all nodes in the left subtree of a node being smaller and all nodes in the right subtree being larger.

Binary search trees are commonly used in computer science and software engineering because they provide an efficient way to search, insert, and delete elements in a data structure. The average and worst-case time complexity for searching, inserting, and deleting elements in a binary search tree is O(log n), where n is the number of nodes in the tree.

The BST property also ensures that the maximum element is in the rightmost leaf node and the minimum element is in the leftmost leaf node, making it easy to find the largest and smallest values in the tree.

However, if the binary search tree is unbalanced, its worst-case time complexity can become O(n), where n is the number of nodes in the tree, rather than the optimal O(log n) time complexity. Thus, it is important to keep the binary search tree balanced to ensure efficient performance.

Advantages of Binary Search Tree

Some advantages of a Binary Search Tree (BST) are:

1. Efficient searching: Since a BST is ordered, it allows for efficient searching for a specific key/value. The worst-case time complexity for searching in a BST is O(log n), where n is the number of nodes in the tree.
2. Efficient insertion and deletion: Similar to searching, insertion and deletion operations can also be performed efficiently on a BST. The worst-case time complexity for insertion and deletion in a BST is O(log n), where n is the number of nodes in the tree.
3. Ordering: The BST property ensures that the tree is ordered, with all nodes in the left subtree of a node being smaller and all nodes in the right subtree being larger. This property can be used to traverse the tree in sorted order.
4. Easy to find minimum and maximum: The minimum and maximum values are always located in the leftmost and rightmost nodes, respectively, making it easy to find them.
5. Memory efficiency: Compared to other data structures like arrays and linked lists, BSTs have relatively low memory overhead, making them memory efficient.
6. Versatility: BSTs can be used to implement various other data structures like priority queues and associative arrays, and are also used in many popular algorithms like binary search, quicksort, and Huffman coding.

However, it is important to keep the binary search tree balanced to ensure efficient performance. An unbalanced tree can lead to worst-case time complexity of O(n) for searching, insertion, and deletion, where n is the number of nodes in the tree.

Basic Operations on Binary Search Trees

Some common operations that can be performed on a Binary Search Tree (BST) are:

1. Search: Search for a given key/value in the BST.
2. Insertion: Insert a new key/value into the BST.
3. Deletion: Delete an existing key/value from the BST.
4. Traversal: Traverse the BST in a specific order, such as inorder, preorder, or postorder, to visit all nodes in the tree.
5. Minimum and maximum: Find the minimum or maximum key/value in the BST.
6. Successor and predecessor: Find the successor or predecessor of a given key/value in the BST.
7. Height: Calculate the height of the BST, i.e., the maximum number of edges from the root node to a leaf node.
8. Size: Calculate the number of nodes in the BST.
9. Checking for balance: Check if the BST is balanced, i.e., the heights of the left and right subtrees of every node differ by at most one.
10. Range queries: Find all key/values in a given range in the BST.
11. Floor and ceiling: Find the floor or ceiling of a given key/value in the BST, i.e., the largest key/value smaller than or equal to or the smallest key/value greater than or equal to the given key/value.

These operations are fundamental to working with binary search trees and are used in many applications.

Binary Search Tree: Search Operation

Here is the step-by-step algorithm and pseudocode for the search operation in a Binary Search Tree (BST):

Algorithm:

1. Start at the root node of the BST.
2. If the root node is null, return null or false.
3. If the key/value to be searched for is equal to the key/value at the root node, return the node or true.
4. If the key/value to be searched for is less than the key/value at the root node, search in the left subtree recursively.
5. If the key/value to be searched for is greater than the key/value at the root node, search in the right subtree recursively.

Pseudocode:

function searchBST(root, key):
    if root is null:
        return null or false
    
    if key == root.key/value:
        return root or true
        
    if key < root.key/value:
        return searchBST(root.left, key)
    else:
        return searchBST(root.right, key)

In the above pseudocode, root is the root node of the BST, key is the key/value to be searched for, and left and right are the left and right subtrees of a node, respectively. The function returns the node containing the key/value if found, or null or false if not found.

The time complexity of the search operation in a BST is O(log n) in the average and best case, where n is the number of nodes in the tree. However, in the worst case, when the BST is unbalanced, the time complexity can be O(n).

Binary Search Tree: Insert Operation

Here is the step-by-step algorithm and pseudocode for the insert operation in a Binary Search Tree (BST):

Algorithm:

1. Start at the root node of the BST.
2. If the root node is null, create a new node with the given key/value and set it as the root node.
3. If the key/value to be inserted is less than the key/value at the root node, insert it in the left subtree recursively.
4. If the key/value to be inserted is greater than the key/value at the root node, insert it in the right subtree recursively.
5. Return the updated root node.

Pseudocode:

function insertBST(root, key):
    if root is null:
        root = new Node(key)
        return root
        
    if key < root.key/value:
        root.left = insertBST(root.left, key)
    else:
        root.right = insertBST(root.right, key)
        
    return root

In the above pseudocode, root is the root node of the BST, key is the key/value to be inserted, and left and right are the left and right subtrees of a node, respectively. The function returns the updated root node after the insertion.

The time complexity of the insert operation in a BST is O(log n) in the average and best case, where n is the number of nodes in the tree. However, in the worst case, when the BST is unbalanced, the time complexity can be O(n).

Binary Search Tree: Delete Operation

Here is the step-by-step algorithm and pseudocode for the delete operation in a Binary Search Tree (BST):

Algorithm:

1. Start at the root node of the BST.
2. If the root node is null, return null.
3. If the key/value to be deleted is less than the key/value at the root node, delete it in the left subtree recursively.
4. If the key/value to be deleted is greater than the key/value at the root node, delete it in the right subtree recursively.
5. If the key/value to be deleted is equal to the key/value at the root node: a. If the root node has no children, simply delete the root node. b. If the root node has only one child, replace the root node with its child. c. If the root node has two children, find the minimum value node in the right subtree (or maximum value node in the left subtree), replace the root node with that node, and delete that node from its original position.

Pseudocode:

function deleteBST(root, key):
    if root is null:
        return null
    
    if key < root.key/value:
        root.left = deleteBST(root.left, key)
    else if key > root.key/value:
        root.right = deleteBST(root.right, key)
    else:
        if root.left is null and root.right is null:
            root = null
        else if root.left is null:
            root = root.right
        else if root.right is null:
            root = root.left
        else:
            temp = findMin(root.right)
            root.key/value = temp.key/value
            root.right = deleteBST(root.right, temp.key/value)
    
    return root
    
function findMin(node):
    while node.left is not null:
        node = node.left
    
    return node

In the above pseudocode, root is the root node of the BST, key is the key/value to be deleted, and left and right are the left and right subtrees of a node, respectively. The findMin function finds the minimum value node in the right subtree.

The time complexity of the delete operation in a BST is also O(log n) in the average and best case, where n is the number of nodes in the tree. However, in the worst case, when the BST is unbalanced, the time complexity can be O(n).

Binary Search Tree: Traversal Operation

There are three common traversal operations in a Binary Search Tree (BST): in-order, pre-order, and post-order traversal. Here are the step-by-step algorithms and pseudocode for each of these traversal operations:

In-order Traversal:

Algorithm:

1. Traverse the left subtree recursively.
2. Visit the root node.
3. Traverse the right subtree recursively.

Pseudocode:

function inOrderTraversal(node):
    if node is not null:
        inOrderTraversal(node.left)
        visit(node)
        inOrderTraversal(node.right)

Pre-order Traversal:

Algorithm:

1. Visit the root node.
2. Traverse the left subtree recursively.
3. Traverse the right subtree recursively.

Pseudocode:

function preOrderTraversal(node):
    if node is not null:
        visit(node)
        preOrderTraversal(node.left)
        preOrderTraversal(node.right)

Post-order Traversal:

Algorithm:

1. Traverse the left subtree recursively.
2. Traverse the right subtree recursively.
3. Visit the root node.

Pseudocode:

function postOrderTraversal(node):
    if node is not null:
        postOrderTraversal(node.left)
        postOrderTraversal(node.right)
        visit(node)

In the above pseudocode, node is a node in the BST, and visit(node) is a function that performs the desired operation on the node (e.g., printing its value).

The time complexity of each traversal operation is O(n), where n is the number of nodes in the tree, since each node is visited exactly once.

Binary Search Tree: Min and Max Element

Finding the minimum and maximum element in a binary search tree can be done in O(h) time, where h is the height of the tree.

Algorithm for finding minimum element in a binary search tree:

1. Start at the root node of the tree.
2. If the left child of the current node exists, move to the left child.
3. If the left child does not exist, then the current node is the minimum node.
4. Repeat steps 2 and 3 until there is no left child.

Pseudocode for finding minimum element in a binary search tree:

function findMin(node):
    if node.left is not null:
        return findMin(node.left)
    else:
        return node

Algorithm for finding maximum element in a binary search tree:

1. Start at the root node of the tree.
2. If the right child of the current node exists, move to the right child.
3. If the right child does not exist, then the current node is the maximum node.
4. Repeat steps 2 and 3 until there is no right child.

Pseudocode for finding maximum element in a binary search tree:

function findMax(node):
    if node.right is not null:
        return findMax(node.right)
    else:
        return node

Binary Search Tree: Size of Tree

The size of a binary search tree is the number of nodes in the tree. To find the size of a binary search tree, we can traverse the entire tree and count the number of nodes.

Algorithm for finding the size of a binary search tree:

1. If the root node is null, the size of the tree is 0.
2. If the root node is not null, recursively find the size of the left and right subtrees.
3. Add 1 to the size of the left and right subtrees and return the total.

Pseudocode for finding the size of a binary search tree:

function treeSize(node):
    if node is null:
        return 0
    else:
        return 1 + treeSize(node.left) + treeSize(node.right)

A Basic C++ Program

Here’s an example C++ program that implements the basic operations (search, insert, delete) for a Binary Search Tree (BST):

#include <iostream>
using namespace std;

// Definition of a BST node
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Function to insert a new node in the BST
TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

// Function to search for a node with a given value in the BST
bool search(TreeNode* root, int val) {
    if (root == nullptr) {
        return false;
    }
    if (root->val == val) {
        return true;
    }
    if (val < root->val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

// Function to find the minimum value in a BST
TreeNode* findMin(TreeNode* root) {
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}

// Function to delete a node with a given value from the BST
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return root;
    }
    if (val < root->val) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        root->right = deleteNode(root->right, val);
    } else {
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        TreeNode* temp = findMin(root->right);
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

// Function to perform in-order traversal of a BST
void inOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

// Test the implementation
int main() {
    TreeNode* root = nullptr;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    
    cout << "In-order traversal of BST: ";
    inOrderTraversal(root);
    cout << endl;
    
    int val = 40;
    if (search(root, val)) {
        cout << "Found " << val << " in BST." << endl;
    } else {
        cout << "Could not find " << val << " in BST." << endl;
    }
    
    cout << "Deleting " << val << " from BST..." << endl;
    root = deleteNode(root, val);
    
    cout << "In-order traversal of BST after deletion: ";
    inOrderTraversal(root);
    cout << endl;
    
    return 0;
}

This above program will output:

In-order traversal of BST: 20 30 40 50 60 70 80 
Found 40 in BST.
Deleting 40 from BST...
In-order traversal of BST after deletion: 20 30 50 60 70 80

We hope this article helped you to understand Binary Search Tree in a very detailed way.

Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.

If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.