Trees

Take the node labels to be distinct. In a full binary tree every node has 0 or 2 children.

• With inorder (A, B): the root is the first node in preorder or the last in postorder, and its position in inorder splits the other nodes into the left and right subtrees. Repeating this rebuilds any binary tree.
• Preorder and postorder (C): for general trees a lone child could be left or right, but here an internal node always has two children. The node after the root in preorder is the left child, and its place in postorder marks where the left subtree ends, so the split is again unique.
• Inorder only (D): the full trees with root 2 (children 1 and 4, where 4 has children 3 and 5) and root 4 (children 2 and 5, where 2 has children 1 and 3) both give 1 2 3 4 5.

Answer: A, B, C

Height here is the number of edges on the longest root-to-leaf path, so a single node has height 0; the bounds in the options use this convention.

• A holds: if \(n_{2}\) nodes have two children, the tree has exactly \(L = n_{2} + 1\) leaves, and those \(n_{2}\) nodes are internal, so \(L \le I + 1\).
• B holds: the longest path alone has \(H + 1\) nodes, and levels 0 to \(H\) hold at most \(1 + 2 + \dots + 2^{H} = 2^{H+1} - 1\) nodes.
• C holds: the first \(H\) nodes on the longest path are internal, and internal nodes can sit only on levels 0 to \(H - 1\), which hold at most \(2^{H} - 1\) nodes.
• D fails: a path of height 2 has a single leaf, so \(H \le L\) breaks, and a perfect tree has \(2^{H}\) leaves, more than \(2^{H-1}\).

Answer: A, B, C