Binary Search Tree (BST) — BST property, insert, search, delete (3 cases): Question bank

Every reveal below uses the Question ::: Answer format: read up to the :::, decide, then check.

Symbols and reference snippets used on this page

Before the traps, here is every symbol and every code fragment this page leans on, defined once so the page stands alone.

Formula Reference snippets (the functions this page names)

def insert(root, v):
    if root is None: return Node(v)          # empty slot found → new leaf
    if v < root.key:  root.left  = insert(root.left, v)
    elif v > root.key: root.right = insert(root.right, v)
    return root                              # v == root.key: duplicate ignored
 
def find_min(node):                          # leftmost node = smallest key
    while node.left is not None: node = node.left
    return node
 
def delete(root, v):
    if root is None: return None
    if v < root.key:  root.left  = delete(root.left, v)
    elif v > root.key: root.right = delete(root.right, v)
    else:                                    # found node to delete
        if root.left  is None: return root.right   # Case 1 & Case 2 (no left)
        if root.right is None: return root.left    # Case 2 (no right)
        succ = find_min(root.right)          # Case 3: in-order successor
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
 
def is_bst(node, low=float('-inf'), high=float('inf')):
    if node is None: return True
    if not (low < node.key < high): return False
    return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)

Three pictures anchor the traps that follow — glance at them now, they'll be referenced by name.

Figure — Binary Search Tree (BST) — BST property, insert, search, delete (3 cases)

True or false — justify

The verdict alone is worthless here. Say why before revealing.

If a node's key is greater than its left child and less than its right child, the whole tree is a valid BST

False — the local child check is not enough. In the "6 under 15" figure (s01), the node 6 passes its parent's check yet is smaller than the ancestor 10 while living in 10's right subtree. Validity needs a

(l o w, hi g h)

range that tightens as you descend.

An in-order traversal of any binary tree gives keys in sorted order

False — this is true only for a valid BST. In-order visits left → node → right, and only the BST invariant guarantees "everything left is smaller, everything right is larger", which is what makes that order sorted.

The same set of keys always produces the same BST shape

False — the shape depends on insertion order. Inserting 10,20,30,40 sorted builds the right-leaning stick in figure s02 of height

n - 1

; inserting them balanced (say 20 first) builds a bushy tree of height

\approx lo g_{2} n

Searching a BST is always

O (lo g n)

False — it is

O (h)

, the height (edges on the longest root-to-leaf path). Only a balanced tree has

h \approx lo g_{2} n

. A degenerate "stick" tree has

h = n - 1

, so search degrades to

O (n)

, no better than a linked list.

In a BST, the smallest key is always the leftmost node

True — from the root, every step left moves to strictly smaller keys, so the smallest key sits at the end of the all-left chain. find_min exploits exactly this. Symmetrically the largest is the rightmost node.

Deleting a node with two children removes exactly the two subtrees it pointed to

False — nothing is thrown away. This is Case 3: we copy the in-order successor's key up and delete the successor node instead, which has ≤ 1 child, so both original subtrees stay connected and sorted.

Inserting a key that already exists in the BST adds a second copy as a new leaf

False (in the standard version) — the insert snippet above reaches v == root.key and just returns root, ignoring it. Handling duplicates is a design choice; the plain BST as written simply drops them.

A newly inserted key can become an internal (non-leaf) node

False — insert follows the search path until it "falls off" at a None child and attaches the key there. New keys are always leaves, which is exactly why no existing pointers break.

The in-order predecessor works just as well as the successor for two-child deletion

True — the predecessor is the largest key in the left subtree (rightmost node there). It is bigger than everything else on the left and smaller than everything on the right, so it preserves the invariant just like the successor does.

Every subtree of a valid BST is itself a valid BST

True — the BST property is defined recursively for every node, so any node you point at is the root of a smaller BST that satisfies the same left-smaller / right-larger rule.

Spot the error

Find what's broken and say why it breaks.

"To search, compare with the root; if not equal, search BOTH children to be safe."

The whole point of the invariant is that you never need both sides — one comparison eliminates an entire subtree. Searching both throws away the

O (lo g n)

advantage and makes it

O (n)

"For Case 3 delete (two children), I'll copy the predecessor's value but then delete the successor node."

You must delete the exact node whose key you copied, in its subtree (predecessor → left subtree, successor → right subtree). Mixing them either duplicates a key or leaves the copied key still present, breaking the invariant.

"is_bst only needs to check left.key < key < right.key at each node."

This is the classic local-only trap (figure s01). It misses ancestor constraints — a node can satisfy its parents yet violate a grandparent. Correct validation carries a shrinking

(l o w, hi g h)

range down the recursion.

"After deleting a leaf I set the node itself to None inside the function."

Setting the local variable to None doesn't update the parent's pointer. The removal must happen by returning the new subtree (return None) so the parent's root.left/root.right is reassigned.

"The in-order successor might have a left child I need to reattach."

It cannot. The successor is the leftmost node of the right subtree — if it had a left child, that child would be smaller and thus the real leftmost. So it has no left child, meaning deleting it is always Case 1 or 2 (see the splice in figure s03).

"To delete key v, I recurse into the left subtree whenever v <= root.key."

Using <= sends you left even when v == root.key, so you'd walk past the node you're trying to delete and never find it. Equality must trigger the delete logic, not a direction.

"Inserting always keeps the tree balanced because we descend one path."

Descending one path keeps insert cheap (

O (h)

) but does nothing to keep it balanced. Adversarial (e.g. sorted) input still produces a stick. Balancing needs AVL Tree or Red-Black Tree rotations.

Why questions

The reasoning IS the answer here.

Why does a single comparison at a node let us discard a whole subtree?

Let

t

be the target key we seek and

k

the key at the current node. If

t < k

, the entire right subtree holds keys

> k > t

, so

t

can't be there — we discard it without looking. One comparison, half the tree gone.

Why is delete for a two-child node (Case 3) reduced to deleting a node with ≤ 1 child?

We swap in the in-order successor, which is the leftmost node of the right subtree and therefore has no left child. Deleting it is Case 1 or 2, so the hard case never recurses into another hard case.

Why does return root.right elegantly handle both the leaf case (Case 1) and the one-child-no-left case (Case 2)?

If the node is a leaf, root.right is None, so the parent's pointer becomes None (leaf removed). If it has only a right child, root.right is that child, which gets spliced up. One line, two cases.

Why is in-order traversal the right sanity check for BST validity?

A valid BST's in-order walk is strictly increasing. If you traverse in-order and ever see a value that isn't greater than the previous, the property is violated somewhere — a cheap

O (n)

test over all

n

nodes.

Why do we prefer a BST over a plain Binary Search on Sorted Array?

Both give

O (lo g n)

search, but the sorted array needs

O (n)

shifting for insert/delete. A BST supports all three in

O (h)

without shifting, staying dynamic as the data set changes.

Why does inserting sorted keys produce the worst case?

Each new key is larger than all previous, so it always attaches to the right, forming the one-sided chain of figure s02. Height grows to

h = n - 1

, and every operation degrades to

O (n)

— the very case balancing trees exist to prevent.

Why must the validation range tighten as we recurse rather than stay fixed?

Every ancestor imposes a bound. Going left of a node with key

k

means everything below must stay

< k

, so we set high = k; going right sets low = k. Fixed bounds would miss these inherited constraints.

Edge cases

Boundaries that break naive assumptions.

Search or delete on an empty tree (root is None)

Search returns None (not found) and delete returns None (nothing to remove) immediately. The base case if node is None handles this before any comparison — no special-casing needed.

Deleting a node with only a left child (no right child)

This is Case 2. The snippet reaches if root.right is None: return root.left, splicing the lone left child straight up to the parent. The mirror of the no-left case.

Deleting a node with only a right child (no left child)

Also Case 2, handled by if root.left is None: return root.right — the same line that also covers a leaf (where root.right is None). Both one-child directions are explicitly caught.

Deleting the root when it's the only node

It's a leaf (Case 1); root.left is None so return root.right returns None, and the caller reassigns the tree to None. The whole tree correctly becomes empty.

Deleting the root when it has two children

Case 3 applies exactly as inside the tree: copy the successor's key into the root and delete the successor from the right subtree; the returned node (same object, new key) stays the root. No special root handling is required.

A tree consisting of a single all-left or all-right chain

This is the degenerate "stick" of figure s02 — height

h = n - 1

. It's still a valid BST (in-order is sorted), but every operation is

O (n)

. Validity and efficiency are separate properties.

Duplicate insertion in the standard implementation

The v == root.key branch does nothing, so the tree is unchanged and the key count

n

stays the same. Any duplicate policy (count field, always-right, etc.) is an intentional extension, not default behaviour.

The in-order successor when the deleted node's right child has no left subtree

Then the right child itself is the leftmost node of the right subtree, so it IS the successor. find_min stops immediately and we splice around it — still Case 1 or 2.

Recall Fast self-test

Cover the answers and reproduce the reason (not just the verdict) for: (a) the local-child validation trap, (b) why successor deletion never recurses into another two-child case, (c) why sorted insertion is worst-case. Reason for (a) ::: local checks miss ancestor bounds; need a shrinking $(l o w, hi g h)$ range. Reason for (b) ::: successor is leftmost of right subtree → no left child → Case 1 or 2. Reason for (c) ::: each key attaches right, forming a height $h = n - 1$ stick.

Related depth: Recursion on Trees, Tree Height vs Depth, Heap vs BST, Binary Tree — terminology & traversals.