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

0 · Recall Warm-up

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

• Which traversal of a BST is sorted? from Lesson 4.5.1
• How many binary tree shapes have 3 nodes? from Lesson 4.3.3
• What is the minimum height of a binary tree with n nodes? from Lesson 4.2.2

1 · The Hook

🎣

A library catalogue receives new books throughout the year. Each new title walks down the catalogue tree as if it were being searched for, and is filed where the search falls off the bottom. The final shape depends entirely on the order in which books arrived.

2 · Predict First

🤔

Insert 50, 30, 70, 20, 40, 60, 80, 65 into an empty BST. Which node becomes the parent of 65? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

60: 65 > 50 → right; 65 < 70 → left; 65 > 60 → right, which is empty: 65 becomes 60’s right child.

Insertion

Search for the key; when the search reaches NULL, put the new node there. A new key always becomes a leaf. O(h).

struct tnode *insert(struct tnode *t, int x)
{
    if (t == NULL) return mk(x, NULL, NULL);
    if (x < t->data) t->left = insert(t->left, x);
    else             t->right = insert(t->right, x);
    return t;
}
void in(struct tnode *t)  { if (!t) return; in(t->left); printf("%d ", t->data); in(t->right); }
void pre(struct tnode *t) { if (!t) return; printf("%d ", t->data); pre(t->left); pre(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]);
    pre(root); printf("\n");
    in(root);  printf("\n");
    return 0;
}

Output

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

Building from a sequence

Insert the keys one by one. The first key is the root forever. The tree is determined by the order: 50 30 70 … gives a bushy tree; the same keys in increasing order give a right-skewed chain.

Best and worst height

• Best case: about log₂ n (a complete-looking tree), e.g. 4 2 6 1 3 5 7 → height 2.
• Worst case: n − 1, when the keys arrive sorted (or reverse sorted, or zig-zag): 1 2 3 4 5 6 7 → height 6. Then search, insert and delete all cost O(n), like a linked list.
• Inserting n keys costs O(n log n) when the tree stays balanced, O(n²) in the worst case.

Lesson 4.6 shows how to keep the height logarithmic automatically.

4 · Visual

Insertion order 4 2 6 1 3 5 7: height 2.

Insertion order 1 2 3 4 5: a chain, height 4.

Inserting 50 30 70 20 40 60 80 65 step by step (new node in brackets):

[50]     50          50             50                 50
        /           /  \           /  \               /  \
      [30]        30   [70]      30    70           30    70
                                /                  /  \
                              [20]               20  [40]        ... then 60, 80, 65

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

Each key follows the search path and becomes a leaf.

5 · Worked Examples

Example 1 Easy

Insert 15, 10, 20, 8, 12, 17, 25, 6, 11, 13, 22, 27 into an empty BST. What are its height and number of leaves?

Solution

Height 3, leaves 6 (6, 11, 13, 17, 22, 27). Preorder: 15 10 8 6 12 11 13 20 17 25 22 27.

The BST of Example 1.

Example 2 Medium

Which insertion orders of 1 … 7 give height 6?

Solution

Any order in which each new key is a new minimum or a new maximum of the keys so far, e.g. 1 2 3 4 5 6 7, 7 6 5 4 3 2 1, or 1 7 2 6 3 5 4 (zig-zag): every insertion extends the single path.

Example 3 GATE

n keys are inserted into an initially empty BST in increasing order. How many key comparisons are made in total?

Solution

The i-th key compares with all i − 1 earlier keys (a chain): 0 + 1 + … + (n − 1) = n(n − 1)/2, i.e. O(n²).

6 · GATE Traps

⚠️

• A newly inserted key is always a leaf; existing nodes never move.
• The first key inserted stays the root.
• Sorted input produces a skewed tree of height n − 1.
• BST operations are O(h), not automatically O(log n).
• Building from n keys costs n(n − 1)/2 comparisons in the worst case.

8 · Memory Hook

🧠

“New keys fall to the bottom like leaves; order decides the shape.”

9 · Connect the Dots

Lessons 4.5.1–4.5.2 searched and grew BSTs. Removing a key is harder, because a node with two children cannot simply disappear without breaking the ordering. Next lesson answers: how is a key deleted while keeping the BST property?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markInsertion

Where is a new key placed in a BST?

• (A) as a new leaf where the search ends
• (B) at the leftmost position
• (C) always at the root
• (D) in the middle of the longest path

Q2MCQ2 marksOutput

What does this print?

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]);
    pre(root); printf("\n");
    in(root);  printf("\n");
    return 0;
}

• (A) preorder then inorder of the 8-key BST
• (B) the insertion order twice
• (C) inorder twice
• (D) preorder twice

Q3NAT1 markHeight

Keys 10, 20, 30, 40, 50, 60 are inserted in this order into an empty BST. What is its height (edges)?

Numerical answer: ________

Q4NAT2 marksComparisons

How many key comparisons are made in total when 10 keys are inserted in increasing order into an empty BST?

Numerical answer: ________

Q5MSQ2 marksShapes

Insert 8, 3, 10, 1, 6, 14, 4, 7, 13. Which are true?

• (A) The height is 3.
• (B) 13 is the right child of 14.
• (C) 6 is the parent of 4 and 7.
• (D) The root is 8.

11 · Rule Card

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

12 · Concept Ledger

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

BST insertionbuilding a BST from a sequenceskewed BST (worst case)best- vs worst-case height

13 · Answer Vault