Binary Search Tree (BST)
A binary search tree adds a recursive ordering invariant to a binary tree so search, insertion, deletion, and sorted traversal all follow from compare-and-branch reasoning.
The Recursive Ordering Invariant
A binary search tree is a binary tree with an ordering rule at every node: all keys in the left subtree are less than the node value, and all keys in the right subtree are greater than the node value. The rule is recursive, so it must hold for every descendant subtree, not just the immediate children.
That recursive part is the common interview trap. A tree with root 10, left child 5, and a right child 12 under 5 is not a valid BST if 12 sits anywhere in the left subtree of 10. The node 12 is greater than its parent 5, but it violates the ancestor bound from 10.
Why Operations Are O(h)
Search in a BST asks one comparison at each level. If the target is less than the current node, the entire right subtree can be ignored. If it is greater, the entire left subtree can be ignored. Insert follows the same path until it finds a missing child position. Delete also starts with the same search path, then handles the local structural case at the found node.
The cost is O(h), where h is the height of the tree. The invariant removes half of the remaining candidate direction at each balanced level, but the formal bound is about height, not the number of nodes directly.
Inorder Means Sorted
Inorder traversal visits left subtree, then node, then right subtree. In a BST, everything in the left subtree is smaller, and everything in the right subtree is larger, so inorder traversal emits values in sorted ascending order.
This property is more than trivia. It powers kth-smallest queries, validation checks, range reporting, and many conversions between BSTs and sorted arrays. When a problem says BST and sorted output, your first instinct should be inorder.
Balanced vs Skewed Height
A balanced BST with n nodes has height O(log n), so search, insert, and delete are O(log n). A skewed BST can have height O(n), such as inserting 1, 2, 3, 4, 5 into an ordinary BST without rebalancing. It becomes a linked list leaning right.
This is why interview answers should say O(h) first, then specialize it: O(log n) if balanced, O(n) if skewed. That phrasing shows you understand both the data structure invariant and its operational risk.
Key Takeaways
- A BST requires every node to satisfy the left-less and right-greater rule across entire subtrees.
- Search, insert, and delete follow one root-to-leaf path, so their natural bound is **O(h)**.
- Inorder traversal of a BST produces sorted ascending values.
- Balanced trees give **O(log n)** height, while skewed trees degrade to **O(n)** height.