Binary Search Tree Implementation

Key Properties

• Left subtree contains values less than root
• Right subtree contains values greater than root
• Both subtrees are also BSTs

Operations

Search

• Time Complexity: O(log n) average, O(n) worst
• Compare target with current node
• Go left if smaller, right if larger

Insert

• Time Complexity: O(log n) average, O(n) worst
• Find correct position using search logic
• Create new node as leaf

Delete

• Time Complexity: O(log n) average, O(n) worst
• Three cases: leaf node, one child, two children
• For two children: replace with inorder successor