Self-checkedTier 1 21 min readpds.bst

Binary search trees

A binary tree kept in order so that search, insert and delete follow one path from the root. Learn the ordering rule, the three cases of deletion, why the shape (and so the running time) depends on the insertion order, the successor, the k-th smallest, how to rebuild a tree from its preorder, and the common wrong test for whether a tree is a BST.

Why it exists

To find a value in an unsorted list you may have to look at all of it. A sorted array can be searched quickly but is slow to insert into. A binary search tree (BST) keeps the data in a branching structure that is ordered, so that a search only follows one path from the root, and an insertion or deletion changes only a few pointers. When the tree is reasonably bushy, all three operations take time proportional to $\log n$ .

Prerequisites

Binary tree traversals

Precise definitions

Binary search tree. A binary tree with a key in every node such that for every node $x$ : all keys in the left subtree of $x$ are smaller than the key of $x$ , and all keys in the right subtree are larger. (The rule is about whole subtrees, not just the two children. With duplicate keys a convention must be chosen, such as "equal keys go right", and the question will state it. This page uses distinct keys.)
Inorder is sorted. The inorder traversal of a BST lists the keys in increasing order. Conversely (for distinct keys) a binary tree whose inorder is strictly increasing is a BST.
Search for $k$ : compare with the root; if equal stop; if smaller go left; if larger go right; stop at NULL (not found). One path, so the time is $O(h)$ where $h$ is the height.
Minimum is the leftmost node; maximum the rightmost.
Successor of a key: the smallest key larger than it. If the node has a right subtree, it is the minimum of that subtree; otherwise it is the lowest ancestor for which the node lies in the left subtree. The predecessor is the mirror image.
Insert $k$ : search for $k$ ; the search ends at a NULL link; put a new node there. The new node is always a leaf.
Delete $k$ $k$ : find the node $z$ $z$ holding $k$ $k$ , then:
1. No children (leaf): remove it.
2. One child: replace $z$ by its child (the child's whole subtree moves up).
3. Two children: find the inorder successor $m$ (the minimum of the right subtree), copy $m$ 's key into $z$ , then delete $m$ from the right subtree. (Copying the key is fine for plain int keys. CLRS's TREE-DELETE instead relinks the nodes themselves, which matters if other pointers refer to nodes or the nodes carry extra data.) $m$ has no left child, so that deletion is case 1 or 2. (Using the inorder predecessor, the maximum of the left subtree, is equally correct and gives a different tree. A question will state which one it wants.)
Cost. Search, insert and delete all take $O(h)$ . For $n$ keys the height is at least $\lceil \log_2(n+1) \rceil - 1$ and at most $n - 1$ .
The shape depends on the insertion order. The same keys can give a perfectly balanced tree or a chain. Keys inserted in sorted order always make a chain, and the operations then take $\Theta(n)$ . For keys inserted in random order the expected height is $O(\log n)$ . Trees that repair their own shape (AVL, red-black) keep the height $O(\log n)$ in the worst case.
Inserting in preorder order rebuilds the same tree. If you insert the keys of a BST's preorder list one by one into an empty tree, you get back the same tree. Every node is inserted after its ancestors, and no node inserted earlier except its ancestors lies on its search path (the earlier ones are in earlier sibling subtrees), so each node lands exactly where it was. (Postorder fails this test, though its reverse works.)

How it works

Insertion

Insertion is a search that ends by creating a node. The blue list is the path from the root, which is the recursion stack of insert(). Watch the last key, 35: it follows 50, then 30, then 40, and is attached as the left child of 40. Every new node is a leaf.

Inserting keys into a binary search tree

Real run

C source

1#include <stdio.h>

2#include <stdlib.h>

4struct node {

5 int data;

6 struct node *left, *right;

7};

9struct node *insert(struct node *t, int x) {

10 if (t == NULL) {

11 t = calloc(1, sizeof *t);

12 t->data = x;

13 return t;

14 }

15 if (x < t->data)

16 t->left = insert(t->left, x);

17 else if (x > t->data)

18 t->right = insert(t->right, x);

19 return t;

20}

Tree (read from the program's real pointers)

Search path (the nodes the recursion has passed through)

empty

Blue ring = on the call stack (or the search path), amber ring = waiting in the queue, green with a number = already printed (and in which order). The filled node is the one this step is about.

Step 1

reached NULL: a new node holding 50 is created here and returned to be linked in

1 / 36

Keys 50, 30, 70, 20, 40, 60, 35 are inserted one after another by hidden driver code. insert() is the exact code that runs. The call stack shows the search path from the root. Produced by: real execution: the tree, the call stack, the queue and the printed output are read from the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

The shape depends on the order

The same function now gets the keys in increasing order. Each key is larger than everything so far, so it follows the right links all the way down and ends as the right child of the previous key. The result is a chain of height $n - 1$ : a BST that is as slow as a linked list.

Inserting sorted keys makes a chain

Real run

C source

1#include <stdio.h>

2#include <stdlib.h>

4struct node {

5 int data;

6 struct node *left, *right;

7};

9struct node *insert(struct node *t, int x) {

10 if (t == NULL) {

11 t = calloc(1, sizeof *t);

12 t->data = x;

13 return t;

14 }

15 if (x < t->data)

16 t->left = insert(t->left, x);

17 else if (x > t->data)

18 t->right = insert(t->right, x);

19 return t;

20}

Tree (read from the program's real pointers)

Search path (the nodes the recursion has passed through)

empty

Blue ring = on the call stack (or the search path), amber ring = waiting in the queue, green with a number = already printed (and in which order). The filled node is the one this step is about.

Step 1

reached NULL: a new node holding 10 is created here and returned to be linked in

1 / 30

Keys 10, 20, 30, 40, 50 are inserted in increasing order by hidden driver code. insert() is the exact code that runs. Produced by: real execution: the tree, the call stack, the queue and the printed output are read from the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Deletion: leaf, one child, two children

A tree is built from 50, 30, 70, 20, 40, 60, 80, 65, and three keys are deleted. Deleting 20 is the leaf case. Deleting 30 (which now has only a right child 40) is the one-child case: 40 takes its place. Deleting 50, which has two children, copies the successor key 60 (the minimum of its right subtree) into the root and then deletes the old node 60, which has only a right child 65.

Deleting from a binary search tree: leaf, one child, two children

Real run

C source

1#include <stdio.h>

2#include <stdlib.h>

4struct node {

5 int data;

6 struct node *left, *right;

7};

9struct node *minnode(struct node *t) {

10 while (t->left != NULL)

11 t = t->left;

12 return t;

13}

15struct node *delete(struct node *t, int x) {

16 if (t == NULL)

17 return NULL;

18 if (x < t->data) {

19 t->left = delete(t->left, x);

20 } else if (x > t->data) {

21 t->right = delete(t->right, x);

22 } else if (t->left == NULL) {

23 struct node *r = t->right;

24 free(t);

25 return r;

26 } else if (t->right == NULL) {

27 struct node *l = t->left;

28 free(t);

29 return l;

30 } else {

31 struct node *m = minnode(t->right);

32 t->data = m->data;

33 t->right = delete(t->right, m->data);

34 }

35 return t;

36}

Tree (read from the program's real pointers)

Search path (the nodes the recursion has passed through)

empty

Blue ring = on the call stack (or the search path), amber ring = waiting in the queue, green with a number = already printed (and in which order). The filled node is the one this step is about.

Step 1

The tree built from 50, 30, 70, 20, 40, 60, 80, 65. Now delete 20 (a leaf), then 30 (one child left), then 50 (two children).

1 / 30

A tree is built from 50, 30, 70, 20, 40, 60, 80, 65 by hidden code, then 20, 30 and 50 are deleted in that order. minnode() and delete() are the exact code that runs. Produced by: real execution: the tree, the call stack, the queue and the printed output are read from the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Worked examples

EX 1Build a BST and read it three ways

Easy

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *insert(struct node *t, int x) {
    if (t == NULL) {
        t = calloc(1, sizeof *t);
        if (t == NULL) exit(1);
        t->data = x;
        return t;
    }
    if (x < t->data)
        t->left = insert(t->left, x);
    else if (x > t->data)
        t->right = insert(t->right, x);
    return t;
}
 
static void in(const struct node *t) {
    if (t == NULL) return;
    in(t->left);
    printf("%d ", t->data);
    in(t->right);
}
 
static void pre(const struct node *t) {
    if (t == NULL) return;
    printf("%d ", t->data);
    pre(t->left);
    pre(t->right);
}
 
static int height(const struct node *t) {
    if (t == NULL) return -1;
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}
 
int main(void) {
    int keys[7] = {50, 30, 70, 20, 40, 60, 35};
    struct node *root = NULL;
    for (int i = 0; i < 7; i++) root = insert(root, keys[i]);
    in(root);
    printf("\n");
    pre(root);
    printf("\n%d\n", height(root));
    return 0;
}

Output:

20 30 35 40 50 60 70
50 30 20 40 35 70 60
3

Reading it. The inorder list is sorted, as it must be. The preorder list tells the shape: 50 is the root; 30, 20, 40, 35 form the left part (30 is its root, 20 its left child, 40 its right child, 35 below 40); 70 and 60 form the right part. The longest path is 50, 30, 40, 35: height 3.

EX 2Search, and how many nodes it looks at

Easy

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *insert(struct node *t, int x) {
    if (t == NULL) {
        t = calloc(1, sizeof *t);
        if (t == NULL) exit(1);
        t->data = x;
        return t;
    }
    if (x < t->data)
        t->left = insert(t->left, x);
    else if (x > t->data)
        t->right = insert(t->right, x);
    return t;
}
 
static int search(const struct node *t, int key, int *examined) {
    *examined = 0;
    while (t != NULL) {
        (*examined)++;
        if (key == t->data) return 1;
        t = key < t->data ? t->left : t->right;
    }
    return 0;
}
 
int main(void) {
    int keys[7] = {50, 30, 70, 20, 40, 60, 35};
    struct node *root = NULL;
    for (int i = 0; i < 7; i++) root = insert(root, keys[i]);
    int c1, c2;
    int f1 = search(root, 35, &c1);
    int f2 = search(root, 45, &c2);
    printf("%d %d %d %d\n", f1, c1, f2, c2);
    return 0;
}

Output:

1 4 0 3

Reading it. Searching for 35 examines 50, 30, 40 and 35: 4 nodes (found). Searching for 45 examines 50 (go left), 30 (go right), 40 (go right), and the right link of 40 is NULL: 3 nodes examined, then not found. The number of nodes examined is at most the height plus one for a successful search. For an unsuccessful search it is the depth of the last node reached plus one.

EX 3Minimum, maximum, successor and predecessor

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *insert(struct node *t, int x) {
    if (t == NULL) {
        t = calloc(1, sizeof *t);
        if (t == NULL) exit(1);
        t->data = x;
        return t;
    }
    if (x < t->data)
        t->left = insert(t->left, x);
    else if (x > t->data)
        t->right = insert(t->right, x);
    return t;
}
 
static int minimum(const struct node *t) {
    while (t->left != NULL) t = t->left;
    return t->data;
}
 
static int maximum(const struct node *t) {
    while (t->right != NULL) t = t->right;
    return t->data;
}
 
static int successor(const struct node *t, int key) {
    int s = -1;
    while (t != NULL) {
        if (key < t->data) {
            s = t->data;
            t = t->left;
        } else
            t = t->right;
    }
    return s;
}
 
static int predecessor(const struct node *t, int key) {
    int p = -1;
    while (t != NULL) {
        if (key > t->data) {
            p = t->data;
            t = t->right;
        } else
            t = t->left;
    }
    return p;
}
 
int main(void) {
    int keys[7] = {50, 30, 70, 20, 40, 60, 35};
    struct node *root = NULL;
    for (int i = 0; i < 7; i++) root = insert(root, keys[i]);
    printf("%d %d\n", minimum(root), maximum(root));
    printf("%d %d %d %d\n", successor(root, 35), successor(root, 40), successor(root, 70), predecessor(root, 50));
    return 0;
}

Output:

20 70
40 50 -1 40

Reading it. The minimum is the leftmost node (20) and the maximum the rightmost (70). To find the successor of a key, walk down from the root as in a search and remember the last node where you went left: that is the smallest key seen that is larger than the target. The successor of 35 is 40 (its parent), of 40 is 50 (the root: 40 has no right subtree, so the answer is the lowest ancestor of which it is in the left subtree), and 70 has no successor (printed as $-1$ ). The predecessor of 50 is the maximum of its left subtree, 40.

EX 4Different insertion orders, different trees

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *insert(struct node *t, int x) {
    if (t == NULL) {
        t = calloc(1, sizeof *t);
        if (t == NULL) exit(1);
        t->data = x;
        return t;
    }
    if (x < t->data)
        t->left = insert(t->left, x);
    else if (x > t->data)
        t->right = insert(t->right, x);
    return t;
}
 
static int height(const struct node *t) {
    if (t == NULL) return -1;
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}
 
static int code, digits;
 
static void pre(const struct node *t) {
    if (t == NULL) return;
    code = code * 10 + t->data;
    digits++;
    pre(t->left);
    pre(t->right);
}
 
int main(void) {
    int orders[6][3] = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}};
    int seen[6], nseen = 0;
    for (int o = 0; o < 6; o++) {
        struct node *root = NULL;
        for (int i = 0; i < 3; i++) root = insert(root, orders[o][i]);
        printf("%d ", height(root));
        code = 0;
        digits = 0;
        pre(root);
        int dup = 0;
        for (int j = 0; j < nseen; j++) dup = dup || seen[j] == code;
        if (!dup) seen[nseen++] = code;
    }
    printf("\n%d\n", nseen);
    return 0;
}

Output:

2 2 1 1 2 2
5

Reading it. The six orders of the keys 1, 2, 3 give heights 2, 2, 1, 1, 2, 2. Only the orders that start with the middle key 2 (2, 1, 3 and 2, 3, 1) give the balanced tree of height 1, and both give the same tree. So the six orders give only 5 different trees, the Catalan number $C_3$ . The six orders are not equally likely to produce each tree: the balanced tree comes from 2 of the 6 orders (the formula $3!/(3 \cdot 1 \cdot 1) = 2$ ), each of the four chains from exactly 1.

EX 5From a preorder list to the postorder

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *insert(struct node *t, int x) {
    if (t == NULL) {
        t = calloc(1, sizeof *t);
        if (t == NULL) exit(1);
        t->data = x;
        return t;
    }
    if (x < t->data)
        t->left = insert(t->left, x);
    else if (x > t->data)
        t->right = insert(t->right, x);
    return t;
}
 
static void post(const struct node *t) {
    if (t == NULL) return;
    post(t->left);
    post(t->right);
    printf("%d ", t->data);
}
 
int main(void) {
    int pre[7] = {50, 30, 20, 40, 70, 60, 80};
    struct node *root = NULL;
    for (int i = 0; i < 7; i++) root = insert(root, pre[i]);
    post(root);
    printf("\n");
    return 0;
}

Output:

20 40 30 60 80 70 50

Reading it. For a BST, the preorder list alone is enough: inserting its keys in that order rebuilds the same tree, and then any other traversal can be read off. By hand, without building the tree: the first key (50) is the root; the keys after it that are smaller (30, 20, 40) form the left subtree and the larger ones (70, 60, 80) the right; repeat inside each part. Postorder lists left subtree, right subtree, root: 20 40 30, 60 80 70, 50.

EX 6The wrong test for a binary search tree

GATE level

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static int local_ok(const struct node *t) {
    if (t == NULL) return 1;
    if (t->left && t->left->data >= t->data) return 0;
    if (t->right && t->right->data <= t->data) return 0;
    return local_ok(t->left) && local_ok(t->right);
}
 
static int bounds_ok(const struct node *t, long lo, long hi) {
    if (t == NULL) return 1;
    if (t->data <= lo || t->data >= hi) return 0;
    return bounds_ok(t->left, lo, t->data) && bounds_ok(t->right, t->data, hi);
}
 
int main(void) {
    struct node *r = mk(10, mk(5, mk(1, NULL, NULL), mk(12, NULL, NULL)), mk(15, NULL, NULL));
    printf("%d %d\n", local_ok(r), bounds_ok(r, LONG_MIN, LONG_MAX));
    return 0;
}

Output:

1 0

Reading it. In this tree every node is larger than its left child and smaller than its right child, so the local test says yes. But 12 is in the left subtree of 10 and is larger than 10, so the tree is not a BST: the rule applies to the whole subtree. The correct test passes down the allowed interval $(lo, hi)$ : going left, the upper bound becomes the node's key; going right, the lower bound becomes the node's key. The starting interval must lie outside every possible key, which is why the code starts with LONG_MIN and LONG_MAX (an arbitrary range such as $\pm 10^6$ would wrongly reject a valid tree that holds a larger key). The simplest equivalent test: the inorder traversal must be strictly increasing.

EX 7The k-th smallest key

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *insert(struct node *t, int x) {
    if (t == NULL) {
        t = calloc(1, sizeof *t);
        if (t == NULL) exit(1);
        t->data = x;
        return t;
    }
    if (x < t->data)
        t->left = insert(t->left, x);
    else if (x > t->data)
        t->right = insert(t->right, x);
    return t;
}
 
static int seen, answer;
 
static void kth(const struct node *t, int k) {
    if (t == NULL || seen >= k) return;
    kth(t->left, k);
    if (++seen == k) answer = t->data;
    kth(t->right, k);
}
 
int main(void) {
    int keys[7] = {50, 30, 70, 20, 40, 60, 35};
    struct node *root = NULL;
    for (int i = 0; i < 7; i++) root = insert(root, keys[i]);
    seen = 0;
    kth(root, 3);
    int a = answer;
    seen = 0;
    kth(root, 6);
    printf("%d %d\n", a, answer);
    return 0;
}

Output:

35 60

Reading it. Inorder visits the keys in increasing order, so the $k$ -th key visited is the $k$ -th smallest. The function counts as it goes and stops descending once the count reaches $k$ . The sorted list is 20 30 35 40 50 60 70, so the 3rd is 35 and the 6th is 60. The time is $O(h + k)$ . The function assumes $1 \le k \le n$ (for a larger $k$ it would silently leave the previous answer in place), and it keeps its state in global variables, so it is not reusable as it stands.

EX 8Deleting keys and reading the preorder after each

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *insert(struct node *t, int x) {
    if (t == NULL) {
        t = calloc(1, sizeof *t);
        if (t == NULL) exit(1);
        t->data = x;
        return t;
    }
    if (x < t->data)
        t->left = insert(t->left, x);
    else if (x > t->data)
        t->right = insert(t->right, x);
    return t;
}
 
static struct node *minnode(struct node *t) {
    while (t->left != NULL) t = t->left;
    return t;
}
 
static struct node *delete(struct node *t, int x) {
    if (t == NULL) return NULL;
    if (x < t->data) {
        t->left = delete(t->left, x);
    } else if (x > t->data) {
        t->right = delete(t->right, x);
    } else if (t->left == NULL) {
        struct node *r = t->right;
        free(t);
        return r;
    } else if (t->right == NULL) {
        struct node *l = t->left;
        free(t);
        return l;
    } else {
        struct node *m = minnode(t->right);
        t->data = m->data;
        t->right = delete(t->right, m->data);
    }
    return t;
}
 
static void pre(const struct node *t) {
    if (t == NULL) return;
    printf("%d ", t->data);
    pre(t->left);
    pre(t->right);
}
 
int main(void) {
    int keys[8] = {50, 30, 70, 20, 40, 60, 80, 65};
    int del[3] = {20, 30, 50};
    struct node *root = NULL;
    for (int i = 0; i < 8; i++) root = insert(root, keys[i]);
    pre(root);
    printf("\n");
    for (int i = 0; i < 3; i++) {
        root = delete(root, del[i]);
        pre(root);
        printf("\n");
    }
    return 0;
}

Output:

50 30 20 40 70 60 65 80
50 30 40 70 60 65 80
50 40 70 60 65 80
60 40 70 65 80

Reading it. Deleting 20 (a leaf) just removes it. Deleting 30, which now has only the right child 40, puts 40 in its place. Deleting 50, which has two children, copies the inorder successor 60 into the root and removes the old 60 node; that node had only a right child 65, which moves up to become the left child of 70. If the predecessor (the maximum of the left subtree, 40) had been used instead, the root would become 40 and the final preorder would be 40 70 60 65 80. Both trees are valid BSTs: which one is expected is stated by the question.

Cheat box

BST: every key in the left subtree $<$ node $<$ every key in the right subtree. Inorder is sorted.
Search, insert, delete: $O(h)$ . Height between $\lceil \log_2(n+1) \rceil - 1$ and $n - 1$ .
Insert: always a new leaf at the end of the search path.
Delete: leaf $\to$ remove; one child $\to$ child takes its place; two children $\to$ copy the inorder successor (min of right subtree) or predecessor (max of left), then delete that node.
Min: leftmost. Max: rightmost. Successor: min of right subtree, else lowest ancestor reached by going left.
Sorted insertion order $\to$ chain. $n!$ orders, $C_n$ trees.
Inserting the preorder list rebuilds the tree. A preorder, a postorder (read in reverse) or a level order alone determines a BST; inorder alone never does (it is just the sorted keys).
To test a BST: pass down $(lo, hi)$ bounds, or check that inorder is strictly increasing. Comparing only with the children is wrong.
$k$ -th smallest: inorder with a counter.

Traps and GATE patterns

Connections

Builds on

Binary tree traversals

Unlocks

Linear and binary searchanalogous to Hashing: functions and collisionscontrasts with B treesPrerequisite of B treesanalogous to Trees and binary treesuses Binary tree traversalsuses Constructing a tree from its traversalsuses Counting binary treesuses Binary heaps and heap operationscontrasts with AVL trees and rotationsPrerequisite of AVL trees and rotationsuses

Across subjects

B treesanalogous-to

Within this subject

AVL trees and rotationsuses Counting binary treesuses Constructing a tree from its traversalsuses Binary heaps and heap operationscontrasts-with

The BST is a binary tree (trees) whose inorder traversal is sorted. How many different BSTs exist is the Catalan question on the counting page, and rebuilding one from a list is on the construction page. Self-balancing versions that keep the height logarithmic are AVL trees. A heap is also a binary tree with an ordering rule, but a weaker one (parent versus children only), which is why it cannot search quickly. Database indexes use the multiway version, B-trees.

PYQs

12 previous year questions from your book. I re-solved each one myself (7 by running or simulating, 5 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2014 · Set 3 · NAT · 2 marksQ22 · page 100 of the book

Suppose we have a balanced binary search tree T
holding n numbers. We are given two numbers L
and H and wish to sum up all the numbers in T that
lie between L and H. Suppose there are m such
numbers in T. If the tightest upper bound on the
time to compute the sum is
O(na logb n + mc logd n)
the value of a + 10b + 100c + 1000d is
.
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
}
The return value of the function is

(a)Θ(n2)
(b)Θ(n2log n)
(c)Θ(n3)
(d)Θ(n3log n)

GATE 2025 · Set 2 · MCQ · 2 marksQ1 · page 146 of the book

A meld operation on two instances of a data
structure combines them into one single instance of
the same data structure. Consider the following
data structures:
P: Unsorted doubly linked list with pointers to the
head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the
worst-case time complexities for meld operation on
instances of size n of these data structures?

(a)P: θ(1), Q: θ(n), R: θ(n)
(b)P: θ(1), Q: θ(nlogn), R: θ(n)
(c)P: θ(n), Q: θ(nlogn), R: θ(n2)
(d)P: θ(1), Q: θ(n), R: θ(nlogn)

year not read yetQ4 · page 66 of the book

Consider a binary search tree (BST) with n leaf nodes
(n > 0). Given any node V, the key present in the node
is denoted as Val(V). All the keys present in the given
BST are distinct. The keys belong to the set of real
numbers.

For a node V, let Suc (V) denote the node that is its
inorder successor. If a node V does not have an
inorder successor, then Suc (V) is NULL. As there are
no duplicates, if Suc (V) is not NULL, then Val(V) <
Val(Suc(V)).
Corresponding to every leaf node L1 that has a non-
NULL Suc (Li), a new key ki with the following
property is to be inserted into the BST.
Val(Li) <ki < Val(Suc(Li))
Let K represent the list of all such new keys to be
inserted into the BST.
Which of the following statements is/are true?

(a)K cannot have any duplicates
(b)K will have at least one element
(c)After inserting all keys from K, the height of the BST can increase at most by one
(d)Number of nodes in the BST will double after inserting all keys from K

GATE 2021 · Set 1Q10 · page 67 of the book

A binary search T contains n distinct elements. What
is the time complexity of picking an element in T that
is smaller than the maximum element in T?

(a)Θ(n)
(b)Θ(log n)
(c)Θ(n log n)
(d)Θ(1)

GATE 2020 · MCQQ11 · page 67 of the book

In a balanced binary search tree with n elements, what
is the worst case time complexity of reporting all
elements in range [a,b]? Assume that the number of
reported elements is k.

(a)Θ(n log k)
(b)Θ(log n + k)
(c)Θ(k log n)
(d)Θ(logn) DATA STRUCTURE

GATE 2016 · Set 2 · MCQQ20 · page 68 of the book

The number of ways in which the numbers 1, 2, 3, 4,
5, 6, 7 can be inserted in an empty binary search tree,
such  that  the  resulting  tree  has  height  6,  is

DATA STRUCTURE

Note: The height of a tree with a single node is 0.
[This question was originally a Fill-in-the-Blanks
question]

(a)2
(b)4
(c)64
(d)32

GATE 2015 · Set 3 · MCQQ26 · page 69 of the book

While inserting the elements 71, 65, 84, 69, 67, 83 in
an empty binary search tree (BST) in the sequence
shown, the element in the lowest level is

(a)65
(b)67
(c)69
(d)83

GATE 2011 · MCQQ35 · page 72 of the book

We are given a set of n distinct elements and an
unlabeled binary tree with n nodes. In how many
ways can we populate the tree with the given set
so that it becomes a binary search tree?

(a)0
(b)1
(c)n!
(d)1 * 2nCn n+1

GATE 2010 · MCQQ36 · page 72 of the book

In a binary tree with n nodes, every node has an
odd number of descendants. Every node is
considered to be its own descendant. What is the
number of nodes in the tree that have exactly
one child?

GATE 2008Q40 · page 72 of the book

You are given the postorder traversal, P, of a binary
search tree on the n elements 1,2,..., n. You have to
determine the unique binary search tree that has P as
its postorder traversal. What is the time complexity of
the most efficient algorithm for doing this?

(a)O(logn)
(b)O(n)
(c)O(nlogn)
(d)none of the above, as the tree cannot be uniquely determined. DATA STRUCTURE

GATE 2007Q42 · page 73 of the book

The maximum number of binary trees that can be
formed with three unlabeled nodes is:

(a)1
(b)5
(c)4
(d)3

GATE 2005Q51 · page 74 of the book

How many distinct binary search trees can be
created out of 4 distinct keys?

(a)5
(b)14
(c)24
(d)42

Self-check

Question 1

Keys 15, 10, 20, 8, 12, 25, 18 are inserted in this order into an empty BST. What is the height, and what is the inorder successor of 15?

Show answer

15 is the root; 10 and 20 are its children; 8 and 12 are under 10; 25 and 18 are under 20 (18 left, 25 right). The height is 2. The successor of 15 is the minimum of its right subtree, 18.

Question 2

A BST on the keys 1 to 7 is a chain (each node has only a right child). How many insertion orders create exactly this tree?

Show answer

Exactly one: the sorted order $1, 2, \ldots, 7$ (formula $7! / (7 \cdot 6 \cdots 1) = 1$ ).

Question 3

A search for 55 in a BST examines the keys 40, 70, 50, 60, 55 in that order. Is this possible?

Show answer

Check the bounds. 40 < 55, go right (all later keys $> 40$ ). 70 > 55, go left (all later $< 70$ ). 50 < 55, go right (all later $> 50$ ). 60 > 55, go left (all later $< 60$ ). 55 fits: $50 < 55 < 60$ . Every step is consistent, so yes, it is possible.

Question 4

Delete the root 50 from the tree with preorder 50 30 20 40 70 60 80 using the inorder successor. What is the new preorder?

Show answer

The tree is perfect. The successor of 50 is the minimum of the right subtree, 60. Copy 60 into the root and delete the old 60 (a leaf). New preorder: 60 30 20 40 70 80.

Question 5

What is the worst-case time to search a BST with $n$ keys, and for which input does it occur?

Show answer

$\Theta(n)$ , when the tree is a chain, for example when the keys were inserted in sorted (or reverse sorted) order.

Revision card

One-screen revision

Left subtree keys $<$ node $<$ right subtree keys (whole subtrees). Inorder sorted.
Search, insert, delete $O(h)$ ; $h$ from $\log n$ to $n - 1$ . Sorted insertion $\to$ chain.
Insert: new leaf at the end of the search path.
Delete: leaf; one child (child moves up); two children (copy successor or predecessor, delete that node).
Min leftmost, max rightmost; successor = min of right subtree or lowest left-turn ancestor.
Preorder (with BST order) rebuilds the tree. $C_n$ BSTs, $n!$ orders.
Validate with bounds or by strictly increasing inorder, not by comparing only with children.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Chapter 12 Binary Search Trees (12.1 What is a binary search tree?, 12.2 Querying, 12.3 Insertion and deletion, 12.4 Randomly built binary search trees)
·Kernighan and Ritchie, The C Programming Language, 2nd ed., Section 6.5 Self-referential Structures

Verification

The three animations replay real runs of the shown insert() and delete() functions: the tree is drawn from the program's left and right pointers, the call stack is the real recursion, and the test suite checks that insertion keeps the inorder sorted, that sorted insertion gives a chain of height n - 1, and that the three deletions leave a valid search tree with the stated keys. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c, also under AddressSanitizer and UBSan (leak detection off; the examples build small trees and do not free them). The number of insertion orders per shape and the number of shapes were checked by trying every insertion order of 1..n for n up to 7 in a one-off script that is not part of the repository. The textbook section numbers were written from memory and have NOT been checked against the books. The prose and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Counting binary trees

Binary heaps and heap operations