Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be n − n…
Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be n − n + 1 1
Show answerHide answer
Correct answer: (C) (n – 1)/2
Explanation
In a full binary tree (each node has 0 or 2 children) with n nodes, the number of internal nodes is I = (n – 1)/2. When the tree is skewed (each internal node has one leaf child), every internal node adds one level, so the maximum height is also (n – 1)/2.