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

NO. Do an in-order walk (left → node → right): visit 5, 10, 6, 15. The sequence 10, 6 is not increasing → invalid. The offending key is 6: it sits in the right subtree of 10 yet 6 < 10, so it violates the property with respect to its ancestor 10, even though 6 < 15 locally passes.

Compare 40 with 50 → 40 < 50, go left. Compare with 30 → 40 > 30, go right. Compare with 40 → equal, found. Sequence of nodes visited: 50, 30, 40. Three comparisons.

Descending each key like a search and dropping it at the first empty slot:

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

In-order (left,node,right) = sorted = 1, 3, 4, 6, 7, 8, 10, 13, 14. Pre-order (node,left,right) = 8, 3, 1, 6, 4, 7, 10, 14, 13. The in-order being sorted is your correctness checkpoint.

Path to 7: 8 (7<8, left) → 3 (7>3, right) → 6 (7>6, right) → 7 (equal). We touch 4 nodes: 4 comparisons. This equals depth-of-7 (=3) plus one.

50 has two children → Case 3. The in-order successor = smallest key in the right subtree = find_min(70's subtree). Right subtree of 50 is 70 with left child 60, so the leftmost is 60. Copy 60 up into the root, then delete the original 60 (a leaf → Case 1):

           60
         /    \
        30     70
       /  \
     20    40

New in-order = 20, 30, 40, 60, 70 ✓ sorted.

Minimum: a perfectly balanced tree of 7 nodes fills levels 0,1,2 completely: $1+2+4=7$. Longest path has $2$ edges → min height $=2=\lfloor {\log }_{2}7\rfloor$. Maximum: a stick — every node has one child. $7$ nodes on one path have $6$ edges → max height $=6=n-1$.

Successor = leftmost node of x's right subtree: go once right, then follow left pointers until None. For 30: right child is 40, which has no left child → successor is 40.

Why enough: the first key is the root; for a BST every later key smaller than the root belongs to the left subtree and every larger one to the right, so the pre-order splits uniquely. Recurse.

• Root 50. Split rest: left group {30,20,40} (all <50), right group {70,60} (all >50).
• Left subtree from 30,20,40: root 30; 20<30 left, 40>30 right → leaves 20,40.
• Right subtree from 70,60: root 70; 60<70 left → leaf 60. Result = exactly Tree A. In-order = 20,30,40,50,60,70 ✓.

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)

Trace (tree 10 → left 5, right 15 → left 6):

• is_bst(10, -∞, ∞) ok → recurse right as is_bst(15, 10, ∞).
• 15 ok → recurse left as is_bst(6, 10, 15).
• Check 10 < 6 < 15? 10 < 6 is False → returns False. The tightened low = 10 (inherited from ancestor 10) is what catches 6. Checking only direct children would miss it.

Order 1 — delete 50, then 70. Delete 50 (two children, successor 60) → Tree from L3·Q1:

      60
     /  \
   30    70
  /  \
20    40

Now delete 70 (a leaf, Case 1) →

      60
     /
   30
  /  \
20    40

Order 2 — delete 70, then 50. Delete 70 first (one child 60, Case 2: splice child up):

      50
     /  \
   30    60
  /  \
20    40

Now delete 50 (two children; right subtree is just 60, so successor = 60, a leaf) →

      60
     /
   30
  /  \
20    40

Both final trees are identical here — the same 4-key BST {20,30,40,60}. But the intermediate shapes differed. In general deletion order can change the final shape when the successor choice differs; this pair happens to converge because the surviving keys admit only one successor at each step.

def find_max(node):        # rightmost node of a subtree
    while node.right is not None:
        node = node.right
    return node
 
# inside delete(), the two-children branch:
pred = find_max(root.left)          # in-order predecessor
root.key = pred.key                 # copy predecessor key up
root.left = delete(root.left, pred.key)   # delete it in LEFT subtree

Why valid: the predecessor is the largest key in the left subtree, so it is larger than every other left-subtree key (left stays $<$ new root) and smaller than every right-subtree key (right stays $>$ new root). Being the rightmost node it has no right child, so deleting it is Case 1 or 2 — the recursion terminates. Crucially you must delete it from the left subtree (mirror of successor→right); mixing sides duplicates a key.

Balanced height $h\approx {\log }_{2}n={\log }_{2}10^6\approx ==20==$, so one search $\approx 20$ comparisons. Worst-case build: inserting sorted keys makes insert $i$ walk a path of length $i-1$. Total $\approx {\sum }_{i=1}^n(i-1)=\frac{n(n-1)}{2}\approx \frac{(10^6{)}^2}{2}=5\times 10^{11}$ comparisons — hopelessly slow. Balanced build (e.g. random order or AVL Tree) costs $O(n\log n)\approx 2\times 10^7$. This is the whole motivation for self-balancing trees.