Questions: Binary Trees

Question 1

A programmer inserts one million records into a binary tree in sorted ascending order. Search operations are far slower than expected — comparable to a linked list. What is the most likely cause?

• A. Binary trees cannot store sorted data; the records should have been stored in a hash table
• B. Inserting in sorted order creates a degenerate tree where each node has only one child, giving height n instead of log₂(n)
• C. The tree exceeded its memory allocation and switched to disk-based storage
• D. Binary tree search is inherently O(n) for datasets above a certain size

Answer: (B)

When sorted values are inserted into a plain binary tree, each new value is the largest seen so far and attaches to the rightmost position — creating a single chain with no branching. The tree degrades to a linked list with height n, so search is O(n) instead of O(log n). This is the central motivation for self-balancing variants like AVL trees and red-black trees, which restructure after insertions to keep height at O(log n) regardless of insertion order.

Question 2

A binary tree has 7 nodes arranged so every level is completely filled. What is the height of this tree (measured as the depth of the deepest node, with the root at depth 0)?

• A. 7 — one unit of height per node
• B. 3 — the number of fully filled levels
• C. 6 — the depth of the deepest node counted starting from 1
• D. 2 — the depth of the deepest node counted starting from 0

Answer: (D)

A completely filled tree with 7 nodes has 3 levels: root at depth 0, two children at depth 1, four grandchildren at depth 2. Height = 2 (depth of the deepest node). Option B confuses height with the number of levels (height + 1). Off-by-one errors in height are common: if height counts edges from root to deepest leaf, a 7-node complete tree has height 2; if it counts nodes along that path, it's 3. The convention used here counts depth from 0.

Question 3

The height of a node in a binary tree is defined as its distance from the root.

• T. True
• F. False

Answer: False

Distance from the root is the node's DEPTH, not its height. Height of a node is the length of the longest path from that node DOWN to a leaf — or equivalently, the height of the subtree rooted at that node. Height of the entire tree equals the depth of the deepest leaf. This confusion is one of the most common binary tree errors: depth measures position going down from the root; height measures how far down the subtree extends further.

Question 4

A full binary tree (most node has 0 or 2 children) is typically also a complete binary tree (most levels filled left-to-right).

• T. True
• F. False

Answer: False

Full and complete are independent properties. A full tree only requires that every internal node has exactly 2 children (no nodes with just 1 child). A complete tree requires every level to be fully filled except possibly the last, filled left-to-right. Example of a full but not complete tree: a root with two children where the left child has two grandchildren and the right child has none. Every node has 0 or 2 children (full), but the levels are not uniformly filled (not complete).

Question 5

Why does the shape of a binary tree — balanced versus degenerate — matter so much for the performance of operations like search and insertion?

Model answer: Most binary tree operations visit nodes along a root-to-target path. The height of the tree determines the maximum length of this path. In a balanced tree, each level doubles the number of nodes, so a tree with n nodes has height approximately log₂(n) — about 20 levels for a million nodes. In a degenerate tree (all nodes in a single chain), height equals n. The difference between O(log n) and O(n) is enormous: searching a million records takes ~20 steps when balanced, up to ~1,000,000 steps when degenerate.

A tree storing identical data in a balanced versus degenerate arrangement has the same information content but wildly different performance. This is why self-balancing tree variants exist: they add structural constraints that guarantee O(log n) height by automatically restructuring after insertions and deletions, preventing the degenerate case regardless of input order.