Operations
Traversals
Help
What is a Binary Search Tree?
- A BST is a binary tree where each node has at most two children
- BST Property: For any node, all values in left subtree are smaller, all values in right subtree are larger
- This property enables efficient search, insert, and delete operations
- BSTs provide O(log n) average-case performance for balanced trees
Operations Explained
- Insert: Start at root, go left if value is smaller, right if larger, until finding empty spot
- Delete: Three cases - leaf node (remove), one child (replace with child), two children (replace with successor)
- Search: Similar to binary search - go left or right based on comparison
- Find Min/Max: Go all the way left for min, all the way right for max
Tree Traversals
- In-Order (Left, Root, Right): Produces sorted sequence for BST
- Pre-Order (Root, Left, Right): Useful for creating copy of tree
- Post-Order (Left, Right, Root): Useful for deleting tree
- All traversals visit every node exactly once - O(n) time complexity
Tree Balance
- Balanced Tree: Height is O(log n), operations are efficient
- Degenerate Tree: Height is O(n), essentially a linked list - operations become O(n)
- Inserting sorted values creates worst-case degenerate tree
- Self-balancing trees (AVL, Red-Black) maintain balance automatically