Binary Search Trees #
- Every node has atmost 2 children
- Left child is less than the parent
- Right child is greater than the parent
- Rotated when the tree is unbalanced
Why unbalanced is a problem? - O(~log N) is not possible in unbalanced tree
Balanced BST #
AVL Trees Red-Black Trees
Operations #
- Typically soft deleted i.e. marked as deleted but the element stays
In-Order traversal - Left -> Root -> Right (recursive) The result will be ascending order
Pre-Order traversal - Root -> Left -> Right (recursive)
Post-Order traversal - Left -> Right -> Root (recursive)