Exploring Time Complexity of BST Operations

This article is a complementary resource to the DSA with Python and DSA with C++ courses.

Exploring Time Complexity of BST Operations

Binary Search Trees (BST) are a fundamental data structure in computer science, widely used for efficient data storage and retrieval.

In this article, we'll examine the time complexity of common BST operations — search, insertion, and deletion.

Search

The search operation in BST involves finding a specific key in the tree.

Python

Java

C++

def search(self, value, current_node=None):

    # Base Case: value not found in tree
    if current_node is None:
        return None

    # Return the current_node if it contains the required value
    if value == current_node.data:
        return current_node

    # Else, if the value is less than current_node,
    # recursively call the left child
    elif value < current_node.data:
        return self.search(value, current_node.left) if current_node.left else None

    # Else, recursively call the right child
    # because the value is greater than current_node
    else:
        return self.search(value, current_node.right) if current_node.right else None

BinarySearchTreeNode<T>* search(T value, BinarySearchTreeNode<T>* current_node) {
    // Base Case: value not found in tree
    if(!current_node) {
        return nullptr;
    }

    // Return the current_node if it contains the required value
    if(value == current_node->data) {
        return current_node;
    }

    // Else, if the value is less than current_node,
    // recursively call the left child
    else if(value < current_node->data) {
        return search(value, current_node->left);
    }

    // Else, recursively call the right child
    // because the value is greater than current_node
    return search(value, current_node->right);
}

Time Complexity of BST Search

The above function recursively moves towards the leaf node from the root until the desired value is found.

In the best case, the value is found in the root. This results in O(1) time complexity.

For all other cases, however, the search operation eliminates half of the remaining tree at each level of recursion. As a result, the number of recursive calls (or comparisons) is proportional to the height of the tree, h.

Thus, the time complexity for BST search is O(h).

Insertion

BST insertion involves two phases:

Finding a place where we can insert the node.
Inserting the node in that position.

Python

Java

C++

def insert_node(self, value, current_node=None):
    if self.root is None:
        self.root = BinarySearchTreeNode(value)
        return
 
    if current_node is None:
        current_node = self.root
 
    if value < current_node.data:
        if current_node.left is None:
            current_node.left = BinarySearchTreeNode(value)
        else:
            self.insert_node(value, current_node.left)
    elif value > current_node.data:
        if current_node.right is None:
            current_node.right = BinarySearchTreeNode(value)
        else:
            self.insert_node(value, current_node.right)

void insert_node(T value, BinarySearchTreeNode<T>* current_node) {
    if (!root) {
      	  root = new BinarySearchTreeNode<T>(value);
        return;
    }

    if (value < current_node->data) {
        if (!current_node->left) {
        	current_node->left = new BinarySearchTreeNode<T>(value);
        }
        else {
            insert_node(value, current_node->left);
        }
    }
    else if (value > current_node->data) {
        if (!current_node->right) {
            current_node->right = new BinarySearchTreeNode<T>(value);
        }
        else {
            insert_node(value, current_node->right);
        }
    }
}

Time Complexity of BST Insertion

Here, the insert_node() function:

Recursively finds the appropriate position in the tree for inserting the new node. It has the same time complexity as search, i.e., O(h).
Adds the new node at that position, which has a time complexity of O(1) because it is just a pointer update.

Here, the search operation dominates the overall computing cost. Thus, the time complexity of this operation is also O(h).

Deletion

To delete a node, we first need to find its position.

Python

Java

C++

def delete_node(self, root, value):
    if not root:
        return root
 
    if value < root.data:
        root.left = self.delete_node(root.left, value)
    elif value > root.data:
        root.right = self.delete_node(root.right, value)
    else:
        if not root.left:
            temp = root.right
        	root = None
        	return temp
        elif not root.right:
            temp = root.left
        	root = None
        	return temp
 
    temp = root.right
    while temp.left:
        temp = temp.left
        root.data = temp.data
        root.right = self.delete_node(root.right, temp.data)
    return root

BinarySearchTreeNode<T>* delete_node(BinarySearchTreeNode<T>* root, T value) {
    if (!root) {
        return root;
    }

    if (value < root->data) {
        root->left = delete_node(root->left, value);
    }
    else if (value > root->data) {
        root->right = delete_node(root->right, value);
    }
    else {
        if (!root->left) {
            BinarySearchTreeNode<T>* temp = root->right;
            delete root;
            return temp;
        }
        else if (!root->right) {
            BinarySearchTreeNode<T>* temp = root->left;
            delete root;
            return temp;
        }

        BinarySearchTreeNode<T>* temp = root->right;

        while (temp && temp->left) {
            temp = temp->left;
        }

        root->data = temp->data;
        root->right = delete_node(root->right, temp->data);
    }

    return root;
}

Time Complexity of BST Deletion

The delete_node() function:

Recursively finds the position of the node to be deleted in the tree. It has the same time complexity of the search operation, i.e., O(h).
Deletes that particular node and updates the pointers. This is a constant time operation, so the time complexity is O(1).

Here, the search operation dominates the overall computing cost. Thus, the time complexity of this operation is also O(h).

Time Complexity: Skewness of the Tree

If the tree is skewed to a single side, it resembles a linked list.

So, we have to traverse all the nodes in the tree. This results in a time complexity of O(n), where n is the number of nodes in the tree.

Binary Search Tree Skewed to a Single Side

So, it's recommended that we have the nodes distributed as uniformly as possible along the left and right side.

Such trees are called balanced trees, where h = logn. Thus, the time complexity is reduced to O(logn).

Summary

In short, here are the time complexities for BST operations in various scenarios:

Scenario	Time Complexity
Average Time Complexity	`O(h)`
BST Skewed on a Single Side	`O(n)`
Balanced BST	`O(logn)`