Trees
Hierarchical structures for sorted data
Binary Search Trees
A Binary Search Tree (BST) maintains the property that for each node, all values in the left subtree are smaller, and all values in the right subtree are larger. This enables O(log n) search, insert, and delete—when the tree is balanced.
BST Property
Left child < Parent < Right child. Inorder traversal gives sorted output.
Balance Matters
An unbalanced BST can degrade to O(n) performance. AVL and Red-Black trees auto-balance.
BST Visualization
Traversals:
Complexity Analysis
| Operation | Balanced BST | Unbalanced (Worst) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Traversal | O(n) | O(n) |
Self-balancing trees (AVL, Red-Black) guarantee O(log n) by maintaining height balance after every operation.