Binary search trees

ACompressed recap

🧾

A BST keeps smaller keys left and larger keys right of every node, so inorder is sorted. Search, insert (new key becomes a leaf), find min/max and delete all cost O(h); h ranges from ⌊log₂ n⌋ to n − 1 (sorted input). Delete: leaf → remove; one child → splice; two children → copy successor (or predecessor) and delete it. Drills: preorder alone rebuilds a BST (insert in that order; postorder in reverse), there are C(n) BSTs on n keys, search paths must stay inside a shrinking interval, and C(L + R, L)·orders(L)·orders(R) insertion orders give the same tree.

BMerged rule card

4.5.1 The BST property; search, minimum, maximum; inorder gives sorted order

• BST: all keys in left subtree node all keys in right subtree, for every node.
• Search: compare, go left/right; O(h).
• Min = leftmost; max = rightmost; O(h).
• Inorder of a BST is sorted (and only BSTs have sorted inorder).
• Successor = min of right subtree (if any).

4.5.2 BST insertion; building a BST from an insertion sequence; best- vs worst-case height

• Insert: search; attach a new leaf at the NULL reached; O(h).
• First key = root; shape depends on insertion order.
• Best height ≈ ⌊log₂ n⌋; worst n − 1 (sorted input).
• Building from n keys: O(n log n) balanced, O(n²) worst; sorted input costs n(n − 1)/2 comparisons.

4.5.3 BST deletion: leaf, one child, two children (inorder successor or predecessor)

• Leaf: remove. One child: splice the child up.
• Two children: copy the inorder successor (min of right subtree) or predecessor (max of left), then delete that node (0 or 1 child).
• Successor and predecessor give different valid BSTs.
• O(h).

4.5.4 BST GATE drills: BST from a preorder/postorder sequence; number of BSTs; valid search paths; insertion orders giving the same BST

• BST from preorder: insert in preorder; from postorder: insert in reverse postorder.
• Inorder of a BST = sorted keys.
• Number of BSTs on n keys = C(n).
• Search path valid iff each key lies inside the interval set by earlier left/right moves.
• Insertion orders giving T: C(L + R, L) × orders(left) × orders(right).
• k-th smallest: k-th node of inorder.

CInterleaved GATE-style questions

Q1NAT1 markHeight

Insert 5, 4, 3, 2, 1 into an empty BST. Height (edges)?

Numerical answer: ________

Q2MCQ2 marksDelete

Deleting 30 (two children 20 and 40) from the lesson BST with the successor rule gives the preorder:

• (A) 50 40 70 60 65 80
• (B) 50 70 60 65 80
• (C) 50 40 20 70 60 65 80
• (D) 50 20 40 70 60 65 80

Q3NAT2 marksCount

How many BSTs on keys 1 … 7 have the key 4 at the root?

Numerical answer: ________

Q4MCQ1 markSearch cost

Searching a BST of height h costs:

• (A) O(n²)
• (B) O(h)
• (C) O(1)
• (D) O(n log n)

Q5MCQ2 marksFrom postorder

A BST has postorder 1 7 5 50 40 10. The root’s right child is:

• (A) 7
• (B) 5
• (C) 50
• (D) 40

Q6MSQ2 marksSearch paths

Which are valid search paths (last key is the target)?

• (A) 10 80 20 70 30 60 40
• (B) 40 50 45 47
• (C) 50 30 40 20
• (D) 60 25 50 40 35 45

Q7NAT2 marksComparisons

Keys 1 … 8 are inserted in increasing order. Total key comparisons?

Numerical answer: ________

Q8MCQ1 markInorder

The inorder sequence of a BST with keys {9, 3, 14, 1} is:

• (A) depends on the insertion order
• (B) 9 3 14 1
• (C) 14 9 3 1
• (D) 1 3 9 14

Q9NAT1 markk-th

In a BST with keys 5, 12, 3, 19, 8, 1, what is the 4th smallest key?

Numerical answer: ________

DAnswer Vault