A node v in a binary tree has depth 4. What is the height of node v?
A4, because height and depth are measured along the same path from the root
BThe tree's total height minus 4, because depth and height always sum to the tree's height
CCannot be determined — height depends on v's subtree below it, not its distance from the root
D0, because nodes at even depth are always leaves
Depth measures edges from the root down to a node — it tells you how far below the root the node sits. Height measures the longest path from a node down to any of its leaves — it tells you how deep the subtree rooted at that node extends. These are independent: a node at depth 4 could have height 0 (if it is a leaf) or height 10 (if it has a large subtree below it). They sum to the tree's total height only for nodes that lie on the single longest root-to-leaf path.
Question 2 Multiple Choice
Integer keys 1, 2, 3, 4, 5 are inserted in order into an initially empty binary search tree. What is the height of the resulting tree, and what does this reveal?
AHeight 2; the BST insertion algorithm automatically balances after each insertion
BHeight 4; the tree degenerates into a right-leaning chain, giving O(n) search time instead of O(log n)
CHeight 3; BST insertion always produces a tree of height ⌈log₂ n⌉ for n elements
DHeight 5; each new node always becomes a leaf at the maximum possible depth
Inserting sorted keys into a BST is the worst case: each new key is larger than all previous ones, so it always becomes the right child of the current rightmost node. The result is effectively a linked list with height n − 1 = 4. Search now takes O(n) time rather than O(log n). This is why self-balancing structures (AVL trees, red-black trees) exist: they enforce the invariant that height stays O(log n) regardless of insertion order, using rotations to maintain balance after each operation.
Question 3 True / False
The height of a tree equals the depth of its deepest leaf.
TTrue
FFalse
Answer: True
True. The height of a tree is defined as the height of the root, which equals the length of the longest path from the root to any leaf. The deepest leaf is at the end of this longest path, and its depth equals the number of edges from the root to it — the same count as the tree's height. So height of tree = depth of deepest leaf.
Question 4 True / False
In a binary tree, most internal node has exactly 2 children.
TTrue
FFalse
Answer: False
False. 'Binary tree' means each node has *at most* 2 children (degree 0, 1, or 2). A tree is called 'full' if every internal node has exactly 2 children, and 'perfect' if it is full and all leaves are at the same depth — but these are special cases. A binary tree with height h can have as few as h + 1 nodes (a chain where each internal node has exactly one child) or as many as 2^(h+1) − 1 nodes (a perfect tree).
Question 5 Short Answer
Explain why an unbalanced binary search tree can degrade to O(n) search time, and why this makes the tree's height the critical structural property for performance.
Think about your answer, then reveal below.
Model answer: In a BST, search works by comparing the target key to the current node and moving left or right. The number of comparisons is at most the height of the tree — the length of the longest root-to-leaf path. In a balanced tree, height is O(log n), so any element can be found in at most log₂(n) comparisons. But if the tree is unbalanced — for example, all nodes in a right-leaning chain from sorted insertion — height is O(n) and search degenerates to a linear scan. Balance ensures the exponential capacity of trees (2^h nodes at height h) is fully exploited, keeping height logarithmic in the number of elements.
Height directly determines worst-case search cost. A perfectly balanced binary tree of height 20 can hold over a million nodes and find any element in at most 20 comparisons. The same million-node tree inserted in sorted order has height ~1,000,000 and may require a million comparisons in the worst case. This is why AVL trees, red-black trees, and B-trees enforce balance invariants: they guarantee O(log n) height regardless of insertion order by performing rotations or rebalancing after each modification.