BST — worst case O(n) — motivation for balancing: Question bank

Figure — BST — worst case O(n) — motivation for balancing

True or false — justify

Every item is stated as a claim. The answer says true or false AND why — never a bare verdict.

A BST guarantees

O (lo g n)

search.

False. A plain BST only guarantees

O (h)

, and

h

can reach

n - 1

on sorted input; only self-balancing BSTs force

h = O (lo g n)

The cost of a BST search depends on how many keys you stored.

False. It depends on the tree's height

h

, not the count

n

directly — the same

n

keys can give

h = ⌊ lo g_{2} n ⌋

h = n - 1

depending on shape.

Inserting keys in decreasing order also produces a degenerate stick.

True. Each key is smaller than everything so far, so it always goes left — a left-leaning stick with

h = n - 1

, just as sorted-increasing gives a right-leaning one.

A tree with height

0

contains no nodes.

False. Height counts edges; a single lone node has height

0

(zero edges on its longest path). The empty tree is the one with height

- 1

If two BSTs store the same keys, they have the same height.

False. Shape depends on insertion order; identical key sets can yield

h = n - 1

h = ⌊ lo g_{2} n ⌋

, differing by a factor of

n

The height of a BST can exceed

n - 1

False. With

n

nodes and one per level you already use levels

0

n - 1

; more height would need

\geq n + 1

nodes, which we don't have.

A perfectly balanced BST on

n

nodes has height exactly

⌊ lo g_{2} n ⌋

True. Packing each level full lets level

i

hold

2^{i}

nodes, so

n

nodes fit in the fewest levels, giving exactly

h = ⌊ lo g_{2} n ⌋

— the shortest possible tree.

A degenerate BST is strictly worse than a linked list.

False. It is asymptotically the same (

O (n)

search); it's arguably worse only by a constant (extra unused child pointers), not in Big-O.

Balancing changes the keys stored in the tree.

False. Balancing (rotations in AVL Trees — rotations and balance factor) only rearranges structure while preserving the BST ordering property; the set of keys is untouched.

Spot the error

Each item quotes flawed reasoning. The answer names the exact broken step.

"Search halves the remaining tree each step, so it's always

O (lo g n)

The "halving" only happens when both subtrees are roughly equal — i.e. when the tree is balanced. In a stick, one subtree is empty, so you discard one node, not half.

"There are

2^{i}

nodes on level

i

, so a BST on

n

nodes has height

lo g_{2} n

Level

i

holds at most

2^{i}

nodes; it is not forced to be full. The

⌊ lo g_{2} n ⌋

result is only the best case, not a guarantee.

"Height = number of nodes on the longest root-to-leaf path."

Height counts edges, which is one less than the node count on that path. This off-by-one doesn't change Big-O but breaks base cases (single node has height

0

, not

1

"Random inserts give expected

O (lo g n)

height, so BSTs are safe in practice."

You cannot guarantee your input is random. Sorted or adversarial input (logs, auto-increment IDs) is common and forces

O (n)

— expectation is not a worst-case guarantee.

"To find the max nodes at height

h

, sum

2^{h}

over the levels: it's

2^{h + 1}

The geometric sum

\sum_{i = 0}^{h} 2^{i}

equals

2^{h + 1} - 1

, not

2^{h + 1}

(see Geometric series). The missing

- 1

matters at small

h

"A BST with

h = n - 1

still throws away half the keys per comparison."

In a stick every node has one child, so each comparison eliminates only the current node — one key, not half. That's exactly why it collapses to

O (n)

"Since inserts and searches both cost

O (h)

, and deletes rebuild the tree, deletes must cost

O (n)

Deletes also just walk one root-to-node path (plus a local fixup), so they are

O (h)

too — no full rebuild.

Why questions

Each answer gives the mechanism, not just a label.

Why does sorted insertion produce the worst case?

Every new key is larger (or smaller) than all previous ones, so it always turns the same direction and never branches — the tree stretches into a one-node-per-level stick with

h = n - 1

Why is BST cost tied to height rather than to

n

Every operation follows a single path from root down to one node, and the longest such path has length

h

; the total node count

n

only matters through how it shapes

h

Why can level

i

hold at most

2^{i}

nodes?

Each node has at most

2

children, so the node count can at most double each level down:

2^{0}, 2^{1}, \dots, 2^{i}

Why does a plain BST fail to guarantee

O (lo g n)

Its shape is decided by the (uncontrollable) insertion order, and one bad order collapses it to a stick; without automatic restructuring nothing prevents that.

Why do self-balancing trees restore the

O (lo g n)

guarantee?

On each insert/delete they detect leaning and perform rotations that pull height back toward

lo g n

, so

h = O (lo g n)

holds regardless of input order (see Red-Black Trees).

Why is the geometric series

2^{0} + \dots + 2^{h} = 2^{h + 1} - 1

central to the best case?

It counts the maximum nodes that fit in

h + 1

full levels; inverting it gives the smallest height that can hold

n

nodes, namely

h = ⌊ lo g_{2} n ⌋

Why is a degenerate BST as slow as a linked list for search?

With one child per node there is no branching to exploit, so searching means walking every node in order — the exact behaviour of a linked list,

O (n)

Why does binary search on a sorted array stay

O (lo g n)

while a BST on sorted input does not?

Binary search on an array always jumps to the true middle index; a BST's "middle" is whatever the root happens to be, and a stick's root is an endpoint, so no halving occurs.

Edge cases

Boundary and degenerate inputs the topic invites.

What is the height of an empty BST?

By our fixed convention,

h = - 1

(no nodes, no path); the point is search costs

O (0)

work — there's nothing to walk.

What is the height of a BST with exactly one node?

0

, since the longest root-to-leaf path has zero edges; both best-case

⌊ lo g_{2} 1 ⌋ = 0

and worst-case

n - 1 = 0

agree here.

For

n = 2

, are the best and worst cases the same?

Yes. Two nodes can only form a root with one child, so

h = 1

always;

⌊ lo g_{2} 2 ⌋ = 1

and

n - 1 = 1

coincide — shape can't vary yet.

At what

n

does the best-vs-worst height gap first appear?

n = 3

: best case

h = ⌊ lo g_{2} 3 ⌋ = 1

(root with two children) versus worst case

h = 2

(a stick) — the first size where insertion order truly matters.

If you insert the same key twice into a BST, what happens to height analysis?

Duplicates are typically rejected or sent consistently one direction; either way the bounds

⌊ lo g_{2} n ⌋ \leq h \leq n - 1

still hold for the distinct keys actually stored.

For a stick of

n

nodes, how many comparisons does a worst-case search make?

Up to

n

comparisons (visiting every node), matching the

h + 1 = n

nodes on the path — this is the

O (n)

trap in action.

Does a perfectly balanced tree require

n

to be exactly

2^{k} - 1

No. For other

n

the last level is only partly filled, giving

h = ⌊ lo g_{2} n ⌋

; full "perfect" trees occur exactly when

n = 2^{h + 1} - 1

Recall One-line summary of every trap

Cost $= O (h)$ , and $⌊ lo g_{2} n ⌋ \leq h \leq n - 1$ ; sorted input hits the top, balancing forces the bottom, height counts edges not nodes, and the empty tree has $h = - 1$ .

Connections

Binary Search Tree — definition and property
Tree height and depth
Binary Search — divide and conquer
AVL Trees — rotations and balance factor
Red-Black Trees
Linked List — O(n) search
Big-O notation
Geometric series