How to Validate Insert Delete and Search Binary Search Trees

You solve Binary Search Tree problems by treating the tree as a sorted array that happens to be stored in nodes. If you perform an inorder traversal on any valid BST, you get a sorted sequence of values. Stop trying to memorize complex pointer manipulations and start visualizing the tree as a flattened, sorted list.

The core property

A BST is defined by a simple rule: for any node, all values in the left subtree are smaller, and all values in the right subtree are larger. This is why inorder traversal (Left-Root-Right) always yields a sorted list. If you are asked to validate a BST, do not just check if left.val < root.val < right.val. That is a common trap. You must pass a range (min, max) down the recursion stack. For the root, the range is (-infinity, +infinity). When you move left, the new range becomes (min, root.val). When you move right, it becomes (root.val, max). If a node value falls outside its assigned range, the tree is invalid.

Worked example: Kth smallest

Consider a tree with 5 at the root, 3 as the left child, and 7 as the right child. The left child 3 has a left child 2 and a right child 4. To find the 2nd smallest element, perform an inorder traversal: visit 2, then 3, then 4, then 5, then 7. The 2nd element in this sequence is 3. You can track this by maintaining a counter that decrements every time you visit a node. When the counter hits zero, that node is your answer.

Insertion and deletion

Insertion is straightforward. Start at the root. If the value is smaller than the current node, move left. If it is larger, move right. When you hit a null pointer, place your new node there. Deletion is the only operation that requires care. If the node has no children, just remove it. If it has one child, replace the node with its child. If it has two children, find the inorder successor (the smallest value in the right subtree) or the inorder predecessor (the largest value in the left subtree). Swap the target node with this successor, then delete the successor node. This keeps the tree structure intact without breaking the BST property.

Floor, ceil, and LCA

Finding the floor or ceil of a value k is just a variation of the search algorithm. For the floor, keep track of the largest node value you have seen so far that is less than or equal to k. For the ceil, track the smallest node value greater than or equal to k. The Lowest Common Ancestor (LCA) is even simpler. Start at the root. If both nodes are smaller than the root, move left. If both are larger, move right. The first node you encounter that sits between the two values is your LCA.

The BST rule of thumb

• Inorder traversal is always sorted.
• Validate using a range (min, max) instead of local comparisons.
• Deleting a node with two children requires swapping with the inorder successor.
• LCA is just a search that stops when the path splits.
• Use O(h) time complexity where h is the height of the tree.

If you are stuck on a problem, draw the tree on paper and trace the inorder traversal sequence. Most bugs in BST code happen because the range constraints are ignored or the wrong child is chosen during deletion. Once you see the sorted sequence, the logic for finding the Kth element or the floor becomes obvious.

Go to DSA Tracker and solve the "Validate Binary Search Tree" problem to practice passing range constraints through recursion.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search on Wikipedia.