Questions: Binary Tree Properties: Height, Balance, Completeness

Question 1

You insert the values 1, 2, 3, 4, 5 into a plain (non-self-balancing) binary search tree in that order. What is the height of the resulting tree?

• A. 2 — BSTs automatically balance themselves during insertion
• B. 3 — each level contains one more node than the previous
• C. 4 — each node becomes the right child of the previous, forming a degenerate chain
• D. The height depends only on the number of nodes, not the insertion order

Answer: (C)

Inserting sorted values into a plain BST produces the worst case: a right-leaning chain where every node has one child. With 5 nodes, the height is 4 (number of edges from root to leaf). This degenerate tree has O(n) search, insert, and delete — as slow as a linked list. This is why insertion order matters and why self-balancing trees (AVL, red-black) exist.

Question 2

Which of the following best explains why a complete binary tree can be stored in an array without pointers?

• A. The left-to-right filling rule ensures node i always has children at indices 2i+1 and 2i+2, with no gaps in the array
• B. Complete trees have no wasted memory because every level is fully filled
• C. Array storage works for any binary tree; complete trees are not special in this regard
• D. Complete trees are stored by writing the in-order traversal into consecutive array slots

Answer: (A)

The key is the index formula: in a complete binary tree stored in a 0-indexed array, node i's left child is at 2i+1 and right child is at 2i+2. This works because complete trees fill levels left-to-right with no gaps, guaranteeing that array slots 0 through n-1 are all occupied with valid nodes. Sparse trees would leave holes requiring explicit null slots or pointers. Heaps exploit this exact property.

Question 3

A binary tree with n nodes typically has height O(log n).

• T. True
• F. False

Answer: False

Only balanced trees guarantee O(log n) height. A degenerate tree — formed, for example, by inserting sorted values into a plain BST — has height n−1, which is O(n). The difference matters enormously for performance: a 1,000-node balanced tree has height ~10; a degenerate chain has height 999. O(log n) height requires active balancing (as in AVL or red-black trees) or a structured insertion pattern.

Question 4

A complete binary tree has all levels fully filled except possibly the last, which is filled from left to right.

• T. True
• F. False

Answer: True

This is the definition of a complete binary tree. It distinguishes 'complete' from 'perfect' (all levels fully filled) and 'full' (every node has 0 or 2 children). The left-to-right filling constraint is what enables array storage without gaps and guarantees minimum height ⌊log₂ n⌋ for n nodes. The heap data structure depends entirely on this property.

Question 5

Why does the height of a binary tree matter for algorithm performance, and what is the worst-case height of a plain binary search tree with n nodes?

Model answer: Most tree operations (search, insert, delete) traverse from root to leaf, visiting one node per level. The height is therefore the worst-case number of steps for these operations. For a balanced tree, height is O(log n), giving O(log n) operations. The worst case for a plain BST is height n−1 — a degenerate chain where every node has only one child — which occurs when values are inserted in sorted order. This reduces performance to O(n), equivalent to a linked list.

Height is the performance story for any tree-based data structure. The gap between O(log n) and O(n) is the gap between searching 1,000 nodes in 10 steps versus 999 steps. Self-balancing trees pay a small overhead per insertion to guarantee the O(log n) height bound, which makes all subsequent operations fast regardless of insertion order.