How a Binary Search Tree Works

A Binary Search Tree (BST) is a special type of binary tree that organizes data in a way that makes searching, inserting, and deleting efficient. It is widely used in computer science because it combines the structure of a binary tree with the efficiency of a sorted dataset.

Structure of a BST

A binary search tree is made up of nodes, where each node has:

• A key (or value)
• A reference to a left child
• A reference to a right child

The key property of a BST is:

• Left Subtree Rule: All values in the left subtree of a node are smaller than the node’s value.

• Right Subtree Rule: All values in the right subtree of a node are greater than the node’s value.

This ordering ensures that the tree remains sorted.

Searching in a BST

The search process follows the BST property:

Start at the root node.

Compare the target value with the current node:

• If the target is equal to the node’s value → Found.
• If the target is smaller → Move to the left child.
• If the target is greater → Move to the right child.

Repeat until the value is found or the search reaches a null reference (meaning the value does not exist in the tree).

This process has an average time complexity of O(log n), assuming the tree is balanced.

Insertion in a BST

To insert a new value:

Start at the root and compare the new value with the current node.

If the new value is smaller, go to the left child; if greater, go to the right child.

Repeat until you find an empty spot (null), then insert the new node there.

By maintaining the BST property, the tree remains sorted after insertion.
Deletion in a BST

Deleting a node is slightly more complex and has three cases:

• Leaf Node (no children): Simply remove the node.

• One Child: Remove the node and connect its child directly to its parent.

• Two Children: Find the node’s inorder successor (the smallest value in its right subtree), replace the node’s value with it, and then delete the successor.

Conclusion

A Binary Search Tree is a powerful data structure that enables efficient searching and organization of data. Its simplicity makes it fundamental in computer science, while its limitations highlight the need for more advanced balanced tree structures in real-world applications.