templates · Trees

BST search, insert, delete and validate

  • The tree is a binary search tree: left < node < right everywhere
  • "Insert", "delete", "search", "floor" or "successor" in a BST
  • "Is this a valid BST?" — checking only the parent is not enough

BST property

the one rule

The invariant

Every node's value lies strictly between the limits set by all its ancestors, not just its parent.

write it from memory

The template

search and insert

javajava.util.*
/** Walk down: smaller goes left, bigger goes right. O(h). */static TreeNode search(TreeNode root, int key) {    TreeNode cur = root;    while (cur != null && cur.val != key) {        cur = key < cur.val ? cur.left : cur.right;      // the BST rule picks one side    }    return cur;                                          // null = not in the tree} /** Returns the root of the tree with key added (no duplicates are added). */static TreeNode insert(TreeNode root, int key) {    if (root == null) return new TreeNode(key);          // found the empty spot    if (key < root.val) root.left = insert(root.left, key);    else if (key > root.val) root.right = insert(root.right, key);    return root;                                         // equal: already there}

root.left = insert(root.left, key) re-links the path on the way back up, so you never track a parent.

fill in the blanks — only these lines change per problem

  1. line 5The direction rule. For floor/ceiling, also remember the last node where you went right (or left).
  2. line 15What to do with an equal key: ignore it, count it, or send it to one side, as the problem says.

delete (three cases)

javajava.util.*
/** Returns the root of the tree with key removed. */static TreeNode delete(TreeNode root, int key) {    if (root == null) return null;                       // key not found    if (key < root.val) {        root.left = delete(root.left, key);    } else if (key > root.val) {        root.right = delete(root.right, key);    } else {        if (root.left == null) return root.right;        // 0 or 1 child: lift the other side up        if (root.right == null) return root.left;        TreeNode next = root.right;                      // 2 children: the inorder successor        while (next.left != null) next = next.left;      // smallest value on the right        root.val = next.val;                             // copy it here...        root.right = delete(root.right, next.val);       // ...and delete it from the right    }    return root;}

Leaf or one child: return the other side. Two children: copy the inorder successor's value here, then delete the successor from the right.

fill in the blanks — only these lines change per problem

  1. line 11Which replacement to use: the smallest on the right (successor) or the largest on the left (predecessor).

validate with a range

javajava.util.*
/** Every node must sit strictly inside the (low, high) range its ancestors allow. null = no limit. */static boolean isValid(TreeNode node, Integer low, Integer high) {    if (node == null) return true;    if (low != null && node.val <= low) return false;    // strict: no duplicates allowed    if (high != null && node.val >= high) return false;    return isValid(node.left, low, node.val)             // left side: everything < node.val        && isValid(node.right, node.val, high);}

Integer limits with null = "no limit" handle Integer.MIN_VALUE and MAX_VALUE nodes, which plain int limits get wrong.

fill in the blanks — only these lines change per problem

  1. line 4Strict <= / >= when duplicates are not allowed; relax one side if the problem allows them.

complexity

What it costs

time O(h)
Each step goes down one level, so at most h steps: about log₂ n when balanced, but n for a skewed tree. Validate visits every node, so it is O(n).
space O(h)
The recursion stack for insert, delete and validate. Search is a loop, so O(1).

watch out

Common bugs

  • Validating only left.val < node.val < right.val. A grandchild can still break a limit set higher up.
  • Using int limits like Integer.MIN_VALUE as "no limit". A node holding that exact value then fails.
  • Forgetting to assign the result: writing insert(root.left, key) instead of root.left = insert(root.left, key).

use it

Practise it on

learn it properly