Binary Search Tree
A binary search tree (BST) is a binary tree that satisfies the BST property: for every node X, all values in the left subtree of X are strictly less than X...
The BST Property and Its Guarantee
A binary search tree (BST) is a binary tree that satisfies the BST property: for every node X, all values in the left subtree of X are strictly less than X's value, and all values in the right subtree are strictly greater. This ordering invariant is maintained after every insertion and deletion. It transforms the tree into an efficient search structure because at each node you can discard half the tree by comparing the target value to the current node's value.
Searching in a BST mirrors binary search on a sorted array. Start at the root. If the target equals the current value, return it. If the target is less, recurse into the left subtree; if greater, recurse into the right subtree. On a balanced BST with N nodes, this process visits at most O(log N) nodes. On a degenerate BST (all nodes inserted in sorted order), it degrades to O(N).
In-order traversal of a BST visits nodes in ascending sorted order. This property is used to verify whether a binary tree is a valid BST and to merge two BSTs efficiently.
Insertion, Deletion, and Edge Cases
Insertion in a BST follows the same path as a search. Traverse until you reach a null pointer where the new node should attach, then insert it there. This preserves the BST property by construction.
Deletion is more complex and has three cases. If the node to delete has no children, simply remove it. If it has one child, replace the node with that child. If it has two children, find the in-order successor — the smallest node in the right subtree — copy its value into the current node, then delete the in-order successor from the right subtree (which will have at most one child, making the deletion straightforward).
A subtle edge case: deleting the root when it has two children. The in-order successor becomes the new root value, and the right subtree loses the successor. After deletion, the BST property is preserved. All three cases run in O(H) time where H is the tree height.
Worked Example and Interview Tips
Worked example: given a BST, find the k-th smallest element. Perform an in-order traversal and count nodes as you visit them. When the counter reaches k, return the current node's value. Time complexity is O(H plus K) where H is the height to reach the leftmost node and K is the count. Space complexity is O(H) for the call stack.
An optimized version augments each node with a subtree size. Then the k-th smallest can be found in O(H) without traversing all k nodes: if left subtree size plus one equals k, the current node is the answer; if k is less, recurse left; otherwise recurse right with k adjusted.
Interview tip: always discuss the worst-case scenario for BST operations. An interviewer may ask why you prefer a balanced BST variant (such as AVL or Red-Black) over a plain BST. The answer is that without balancing, a sequence of sorted insertions produces a linked-list-shaped tree where all operations degrade from O(log N) to O(N). Also remember that duplicate handling must be defined explicitly — equal values can go left, right, or be counted, and you should state your convention.