32. Binary Search Trees (BSTs): Insertion and Search

A Binary Search Tree (BST) is a special type of binary tree that organizes data for efficient searching, insertion, and deletion.

The BST Property

For every node X in the tree:

1. The value of all nodes in its left subtree must be less than the value of X.
2. The value of all nodes in its right subtree must be greater than the value of X.

Search Operation

1. Start at the root.
2. If the target is equal to the current node, return true.
3. If the target is smaller, move to the left child.
4. If the target is larger, move to the right child.

Efficiency

• Average Case (Balanced Tree): Search, Insertion, and Deletion are O(log N). (Similar efficiency to Binary Search on an array).
• Worst Case (Skewed Tree): If data is inserted in sorted order, the tree becomes a linked list, and complexity degrades to O(N).