A size-balanced binary tree is a binary tree in which, for every node, the…
PYQ GATE 1997
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 subtrees 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 induction on h, that a size-balanced 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 explanation.
Attempted by 2 students.
Sign up free to check your answer
Sign up freeLoading lesson…

