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

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Deleting a node with two children: what replaces its key? from Lesson 4.5.3
• What is the inorder of any BST? from Lesson 4.5.1
• Which traversal pairs rebuild a unique binary tree? from Lesson 4.3.1

1 · The Hook

🎣

Some GATE BST questions look long but have one-line answers once you see the trick: the inorder of a BST is free (it is the sorted keys), the number of BSTs is a Catalan number, and a search path is valid only if it keeps narrowing an interval.

2 · Predict First

🤔

A BST’s preorder is 30 20 10 15 25 23 39 35 42. What is its postorder? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

15 10 23 25 20 35 42 39 30. Insert the keys in preorder order (or use the sorted inorder with the preorder) to rebuild the tree, then read it in postorder.

BST from preorder (or postorder)

The inorder is the sorted keys, so preorder alone determines a BST. Fastest method: insert the keys in the given preorder order into an empty BST (each parent comes before its descendants, so this rebuilds exactly that tree). For postorder, insert the keys in reverse postorder (that also lists every parent before its descendants).

Number of BSTs on n distinct keys

Choose the root (any key i); the smaller keys form the left BST and the larger the right. The count is the Catalan number C(n): 1, 1, 2, 5, 14, 42 … (the same as binary tree shapes, because each shape has exactly one valid labelling with sorted keys).

Valid search paths

As the search goes down, the key must stay inside an interval: going left after x sets an upper bound x, going right sets a lower bound x. A path is valid if every visited key lies strictly inside the current interval.

Insertion orders that give the same BST

An order produces a given BST iff every node is inserted after its parent. Count: the root first; then the left and right subtrees’ orders can be interleaved in (L + R choose L) ways:

orders(T) = C(L + R, L) × orders(left) × orders(right)

For the BST 4 2 6 1 3 5 7: C(6, 3) × 2 × 2 = 20 × 4 = 80. For 50 30 70 20 40 60 80 65: 210.

k-th smallest

Do an inorder traversal and stop at the k-th node (or count subtree sizes).

int k = 3, seen = 0, ans = -1;
void kth(struct tnode *t)
{
    if (t == NULL || ans != -1) return;
    kth(t->left);
    if (++seen == k) ans = t->data;
    kth(t->right);
}

int main(void)
{
    int a[] = {50, 30, 70, 20, 40, 60, 80, 65}, i;
    struct tnode *root = NULL;
    for (i = 0; i < 8; i++) root = insert(root, a[i]);
    kth(root);
    printf("%d\n", ans);
    return 0;
}

Output

40

4 · Visual

BST rebuilt from preorder 30 20 10 15 25 23 39 35 42.

Search path check for 10 80 20 70 30 60 40 (target 40):

key   move    interval after the move
10    right   (10, +inf)
80    left    (10, 80)
20    right   (20, 80)
70    left    (20, 70)
30    right   (30, 70)
60    left    (30, 60)
40    found   40 lies in (30, 60): valid

Each step narrows the open interval in which the target must lie.

5 · Worked Examples

Example 1 Easy

A BST has postorder 1 7 5 50 40 10. Give its preorder and inorder.

Solution

Insert reverse postorder 10 40 50 5 7 1: preorder 10 5 1 7 40 50; inorder (sorted) 1 5 7 10 40 50.

Example 2 Medium

How many BSTs can be formed with the keys 1 … 6? How many of them have 1 at the root?

Solution

C(6) = 132. With 1 at the root, the other 5 keys form the right subtree: C(5) = 42.

Example 3 GATE

In how many insertion orders of the keys {1, …, 7} does the perfectly balanced BST (root 4; 2, 6; 1, 3, 5, 7) result?

Solution

Root 4 first. Left subtree {1, 2, 3} must start with 2 (2 orders: 2 1 3 or 2 3 1), right subtree likewise 2 orders. Interleave 3 + 3 left/right keys: C(6, 3) = 20. Total 20 × 2 × 2 = 80.

6 · GATE Traps

⚠️

• Preorder (or postorder) alone determines a BST because inorder is the sorted keys.
• Rebuild from postorder by inserting in reverse postorder, not in postorder.
• Number of BSTs on n keys is C(n), not n!.
• A search path must satisfy all earlier bounds, not just the previous key.
• Insertion orders: parent before child; count with C(L + R, L) × orders(L) × orders(R).

8 · Memory Hook

🧠

“Inorder is free; Catalan counts; the interval shrinks.”

9 · Connect the Dots

Every BST operation costs O(h), and the drills showed how easily h becomes n − 1. The last lesson of Phase 4 answers: can a BST repair its own shape after each insertion so that its height always stays about log₂ n?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ2 marksFrom preorder

A BST has preorder 30 20 10 15 25 23 39 35 42. Its postorder is:

• (A) 15 10 23 20 25 35 42 39 30
• (B) 15 10 23 25 20 35 42 39 30
• (C) 10 15 20 23 25 30 35 39 42
• (D) 15 10 25 23 20 35 42 39 30

Q2NAT1 markCount

How many BSTs are there on 5 distinct keys?

Numerical answer: ________

Q3MSQ2 marksSearch path

Which can be the sequence of keys visited when searching a BST for 55?

• (A) 10 75 64 43 60 57 55
• (B) 90 12 68 34 62 45 55
• (C) 9 85 47 68 43 57 55
• (D) 79 14 72 56 16 53 55

Q4NAT2 marksOrders

How many insertion orders of 3, 1, 2, 5, 4 (the keys {1, …, 5}) produce the same BST as inserting them in the order 3 1 2 5 4?

Numerical answer: ________

Q5MCQ2 marksOutput

What does this print?

int k = 3, seen = 0, ans = -1;
void kth(struct tnode *t)
{
    if (t == NULL || ans != -1) return;
    kth(t->left);
    if (++seen == k) ans = t->data;
    kth(t->right);
}

int main(void)
{
    int a[] = {50, 30, 70, 20, 40, 60, 80, 65}, i;
    struct tnode *root = NULL;
    for (i = 0; i < 8; i++) root = insert(root, a[i]);
    kth(root);
    printf("%d\n", ans);
    return 0;
}

• (A) 50
• (B) 20
• (C) 40
• (D) 30

11 · Rule Card

• 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.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

BST from preorder / postordernumber of BSTs = Catalanvalid search path (interval method)insertion orders giving the same BSTk-th smallest via inorder

13 · Answer Vault