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

0 · Recall Warm-up

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

• What does height(NULL) return in the edges convention? from Lesson 4.4
• Which structure gives level order? from Lesson 4.3.2
• How many probes does binary search need in a sorted array of n elements? from Lesson 3.1

1 · The Hook

🎣

Binary search on a sorted array is fast, but inserting into that array means shifting. A linked list inserts easily but cannot be binary-searched. A binary search tree combines the two: every node acts like the middle of a binary search, and new keys hang off the bottom without shifting anything.

2 · Predict First

🤔

In a tree where every node’s left subtree has smaller keys and its right subtree larger keys, how do you find the minimum key? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Start at the root and keep going left until there is no left child. That node holds the minimum (no smaller key can be to its right).

The BST property

A binary search tree (BST) is a binary tree in which, for every node x, every key in x’s left subtree is smaller than x’s key and every key in its right subtree is larger. (Duplicates are either forbidden or sent consistently to one side.) The property must hold for whole subtrees, not just children.

Search

Compare the key with the current node: equal → found; smaller → go left; larger → go right; NULL → absent. One comparison per level: O(h), where h is the height.

struct tnode *search(struct tnode *t, int key)
{
    while (t != NULL && t->data != key) {
        printf("%d ", t->data);                 /* the search path */
        t = (key < t->data) ? t->left : t->right;
    }
    return t;
}
int minKey(struct tnode *t) { while (t->left) t = t->left; return t->data; }
int maxKey(struct tnode *t) { while (t->right) t = t->right; return t->data; }

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]);
    printf("found %d | ", search(root, 65)->data);
    printf("%s | ", search(root, 45) == NULL ? "45 absent" : "45 present");
    printf("min %d max %d\n", minKey(root), maxKey(root));
    in(root); printf("\n");
    return 0;
}

Output

50 70 60 found 65 | 50 30 40 45 absent | min 20 max 80
20 30 40 50 60 65 70 80

Minimum, maximum

Minimum: the leftmost node; maximum: the rightmost node. O(h).

Inorder is sorted

Inorder visits left subtree (all smaller), the node, right subtree (all larger), so it lists the keys in increasing order. Conversely, a binary tree is a BST exactly when its inorder is sorted. This gives the inorder successor of a node: the next key in inorder (the minimum of its right subtree, if it has one).

4 · Visual

BST built from 50 30 70 20 40 60 80 65. The search for 65 visits 50 → 70 → 60 → 65.

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

search 65:  65 > 50 -> right;  65 < 70 -> left;  65 > 60 -> right;  found
search 45:  45 < 50 -> left;   45 > 30 -> right; 45 > 40 -> right (NULL): absent
inorder:    20 30 40 50 60 65 70 80   (sorted)

Every comparison discards one whole subtree.

5 · Worked Examples

Example 1 Easy

In the BST above, find the minimum, maximum and the inorder successor of 60.

Solution

Min 20 (leftmost), max 80 (rightmost). 60 has a right subtree {65}: successor = its minimum, 65.

Example 2 Medium

Is the tree with root 10, left child 5 (whose right child is 12) and right child 15 a BST?

Solution

No. 12 is in 10’s left subtree but 12 > 10. Each parent–child pair looks fine; the property fails for the whole subtree. Its inorder 5 12 10 15 is not sorted.

Example 3 GATE

A BST has height h. What is the maximum number of comparisons for an unsuccessful search, and how many comparisons does the search for 45 above make?

Solution

At most h + 1 key comparisons (one per level, down to a NULL). For 45: 50, 30, 40 → 3 comparisons, then NULL.

6 · GATE Traps

⚠️

• The BST property is about whole subtrees, not just the direct children.
• Inorder of a BST is sorted; preorder and postorder are not.
• Search cost is O(h), which is O(log n) only if the tree is balanced.
• Minimum is the leftmost node, which need not be a leaf (it may have a right child).
• With duplicates, a fixed rule (e.g. equal keys go right) must be used consistently.

8 · Memory Hook

🧠

“Smaller left, larger right — at every level, for the whole family.”

9 · Connect the Dots

Lesson 4.5.1 searched a BST that already existed. Keys usually arrive one at a time. Next lesson answers: where does a new key go, what tree results from a given order of insertions, and how tall can that tree become?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markProperty

Which traversal of a BST outputs the keys in increasing order?

• (A) level order
• (B) inorder
• (C) preorder
• (D) postorder

Q2MCQ2 marksOutput

What does this print?

struct tnode *search(struct tnode *t, int key)
{
    while (t != NULL && t->data != key) {
        printf("%d ", t->data);                 /* the search path */
        t = (key < t->data) ? t->left : t->right;
    }
    return t;
}
int minKey(struct tnode *t) { while (t->left) t = t->left; return t->data; }
int maxKey(struct tnode *t) { while (t->right) t = t->right; return t->data; }

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]);
    printf("found %d | ", search(root, 65)->data);
    printf("%s | ", search(root, 45) == NULL ? "45 absent" : "45 present");
    printf("min %d max %d\n", minKey(root), maxKey(root));
    in(root); printf("\n");
    return 0;
}

• (A) the keys in insertion order
• (B) two lines as shown in the lesson
• (C) only the inorder line
• (D) 50 70 60 found 65 without the rest

Q3NAT1 markComparisons

How many keys are compared when searching for 80 in the BST of this lesson (including the final match)?

Numerical answer: ________

Q4MCQ1 markValidity

Which inorder sequence shows that a binary tree is NOT a BST?

• (A) 2 5 8 11
• (B) 1 3 3 7 (duplicates sent right)
• (C) 10 20 30
• (D) 4 9 6 10

Q5MSQ1 markFacts

Which are true for a BST of height h?

• (A) The minimum is the leftmost node.
• (B) Search takes O(h).
• (C) The minimum is always a leaf.
• (D) The inorder successor of a node with a right subtree is the minimum of that subtree.

11 · Rule Card

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

12 · Concept Ledger

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

binary search tree (BST)BST propertyBST searchminimum / maximuminorder successor / predecessor

13 · Answer Vault