Question 10091 –

A size-balanced binary tree is a binary tree in which for every node, the difference between the number of nodes in the left and right subtree is at most 1. The distance of a node from the root is the length of the path from the root to the node. The height of a binary tree is the maximum distance of a leaf node from the root.
(a) Prove, by using induction on h, that a size-balance binary tree of height h contains at least 2^h nodes.
(b) In a size-balanced binary tree of height h≤1, how many nodes are at distance h−1 from the root? Write only the answer without any explanations.

Correct Answer: A