[/learnings]

DSA: Binary Search Trees

Saturday, 5 September 2026

Learning the ordering invariant, operations, and applications of Binary Search Trees.

{data-structures-and-algorithms}{tree}{binary-search-tree}

Binary Search Tree

A Binary Search Tree (BST) is a binary tree with an additional ordering rule. For every node:

every value in the left subtree  < node value
every value in the right subtree > node value

              8
           /     
          3      10
        /         
       1    6       14
           /       /
          4   7    13

For example, 4 is valid below 6 because it is smaller than 6, but it is also larger than 3 and smaller than 8. A value must satisfy the constraints created by every ancestor on its path.

Why a BST is useful

At each node, comparison removes one entire subtree from consideration:

search for 7:

8  ->  7 < 8, go left
3  ->  7 > 3, go right
6  ->  7 > 6, go right
7  ->  found

That is binary search but on trees. It is fast only when the tree is reasonably balanced.

Search

To search for target:

  1. If the current node is null, the value is absent.
  2. If target == node->val, it is found.
  3. If target < node->val, continue in the left subtree.
  4. Otherwise, continue in the right subtree.
TreeNode* searchBST(TreeNode* root, int target) {
  while (root && root->val != target) {
    root = target < root->val ? root->left : root->right;
  }
  return root;
}

Insert

Insertion follows the same path as search, stopping at a missing child. The new value is attached there as a leaf, which preserves the BST invariant.

insert 5 into:          after insertion:

       8                       8
      /                      / 
     3  10                   3  10
                             
       6                       6
                              /
                             5

Minimum and maximum

The smallest value is the leftmost node; the largest is the rightmost node.

minimum: keep moving left until left is null
maximum: keep moving right until right is null

In-order traversal is sorted

In-order traversal visits:

left subtree -> node -> right subtree

Because every left-subtree value is smaller and every right-subtree value is larger, an in-order traversal of a valid BST returns values in strictly increasing order.

in-order of the example: 1 3 4 6 7 8 10 13 14

This fact powers several common operations:

Successor and predecessor

The in-order successor of a node is the next larger value. The in-order predecessor is the next smaller value.

For a node with a right subtree, its successor is the leftmost node of that right subtree.

       8
        
        10
       /
      9

successor of 8 = 9

For a node with a left subtree, its predecessor is the rightmost node of that left subtree. If the required subtree does not exist, walk down from the root and remember the last ancestor that could be the answer.

Validate a BST

Comparing a node only with its immediate children is not enough.

        8
       / 
      3  10
       
        9

9 is larger than its parent 3, but it is in the left subtree of 8, so the tree is invalid.

The reliable method passes an allowed range down the tree:

root:          (-infinity, +infinity)
left of 8:     (-infinity, 8)
right of 8:    (8, +infinity)
right of 3:    (3, 8)

Every node must lie strictly inside its range.

Lowest Common Ancestor in a BST

The Lowest Common Ancestor (LCA) of two nodes is the deepest node whose subtree contains both nodes.

The ordering rule makes this simpler than LCA in a general binary tree:

if p and q are both smaller than root: go left
if p and q are both larger than root:  go right
otherwise: root is the LCA

The “otherwise” case means the two values split at the current node, or one of them is the current node.

Delete

Deletion is the core BST operation because the ordering must still hold afterwards.

Case 1: leaf node

Remove it directly.

    6                 6
   /       ->         
  4   7                 7

Case 2: node with one child

Connect its parent directly to its only child.

    6                 7
     
      7

Case 3: node with two children

Replace the node’s value with its in-order successor: the smallest value in its right subtree. Then delete that successor from its original position. The successor has no left child, so its final deletion is Case 1 or Case 2.

        8                    10
       /       ->          /  
      3  10                3   14
          
          14

The in-order predecessor—the largest value in the left subtree—works equally well. Choose one convention and apply it consistently.

Complexity

Let h be the height of the tree. | Operation | Time | Extra space, iterative | |---|---:|---:| | Search | O(h) | O(1) | | Insert | O(h) | O(1) | | Minimum / maximum | O(h) | O(1) | | Successor / predecessor | O(h) | O(1) | | Delete | O(h) | O(1) | | In-order traversal | O(n) | O(h) |

For a balanced tree, h = O(log n). For a completely skewed tree, h = O(n).

balanced:                 skewed after sorted insertion:

       4                         1
     /                           
    2     6                        2
   /    /                         
  1  3 5  7                        3
                                    
                                     4

Leetcode Practice

quantinium © 2026