Question:
The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is __________. (answer in integer)
The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is __________. (answer in integer)
Show Hint
A full binary tree needs an odd number of nodes, with \(N = 2I+1\) for \(I\) internal nodes. To maximize height for a fixed \(N\), build a caterpillar shaped tree, whose minimum node count for height \(h\) is \(2h+1\); solve \(2h+1 \le N\) for the largest integer \(h\).
Updated On: Jul 22, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 11
Solution and Explanation
Step 1: Recall the definition of a full binary tree.
A full binary tree (also called a strict binary tree) is one in which every node has either exactly 0 children (a leaf) or exactly 2 children (an internal node). No node is allowed to have exactly 1 child.
Step 2: Use the leaf-internal node relationship.
For any full binary tree, if \(I\) is the number of internal nodes (each contributing exactly 2 children) and \(L\) is the number of leaves, then \(L = I + 1\). The total number of nodes is \(N = I + L = 2I + 1\), which is always odd. Here \(N = 23\) is odd, consistent with this, giving \(I = 11\) and \(L = 12\).
Step 3: Identify the shape that maximizes height for a fixed number of nodes.
To get the tallest possible full binary tree from a fixed node budget, the tree should use as few nodes as possible at each level while still respecting the full binary tree rule. This is achieved by a caterpillar shaped tree: at every level except the deepest, one internal node has exactly one child that is a leaf (using up a node without extending the depth) and one child that continues the path downward to the next level, until finally the path ends in a single leaf at the bottom.
Step 4: Find the minimum number of nodes needed to reach a given height \(h\) with this caterpillar shape.
Each of the \(h\) internal spine nodes contributes exactly one extra leaf sibling, and the spine itself has \(h+1\) nodes from the root down to the final leaf at depth \(h\). Counting carefully, the minimum node count for a full binary tree of height \(h\) is \(2h + 1\) (this matches small cases: height 1 needs 3 nodes, that is, a root with two leaf children; height 2 needs 5 nodes).
Step 5: Find the maximum height achievable with 23 nodes.
We need the largest \(h\) such that \(2h + 1 \le 23\), which gives \(h \le 11\). At \(h = 11\), the minimum node requirement is exactly \(2(11) + 1 = 23\), matching the available node count exactly, so a full binary tree of height 11 using precisely 23 nodes exists (the caterpillar shape itself, with no nodes left over that would need to be placed elsewhere).
Step 6: Rule out height 12.
Height 12 would require at least \(2(12) + 1 = 25\) nodes, which exceeds the available 23 nodes, so height 12 is not achievable.
Step 7: Conclusion.
The maximum possible height of a full binary tree with 23 nodes is 11.
\[ \boxed{11} \]A full binary tree (also called a strict binary tree) is one in which every node has either exactly 0 children (a leaf) or exactly 2 children (an internal node). No node is allowed to have exactly 1 child.
Step 2: Use the leaf-internal node relationship.
For any full binary tree, if \(I\) is the number of internal nodes (each contributing exactly 2 children) and \(L\) is the number of leaves, then \(L = I + 1\). The total number of nodes is \(N = I + L = 2I + 1\), which is always odd. Here \(N = 23\) is odd, consistent with this, giving \(I = 11\) and \(L = 12\).
Step 3: Identify the shape that maximizes height for a fixed number of nodes.
To get the tallest possible full binary tree from a fixed node budget, the tree should use as few nodes as possible at each level while still respecting the full binary tree rule. This is achieved by a caterpillar shaped tree: at every level except the deepest, one internal node has exactly one child that is a leaf (using up a node without extending the depth) and one child that continues the path downward to the next level, until finally the path ends in a single leaf at the bottom.
Step 4: Find the minimum number of nodes needed to reach a given height \(h\) with this caterpillar shape.
Each of the \(h\) internal spine nodes contributes exactly one extra leaf sibling, and the spine itself has \(h+1\) nodes from the root down to the final leaf at depth \(h\). Counting carefully, the minimum node count for a full binary tree of height \(h\) is \(2h + 1\) (this matches small cases: height 1 needs 3 nodes, that is, a root with two leaf children; height 2 needs 5 nodes).
Step 5: Find the maximum height achievable with 23 nodes.
We need the largest \(h\) such that \(2h + 1 \le 23\), which gives \(h \le 11\). At \(h = 11\), the minimum node requirement is exactly \(2(11) + 1 = 23\), matching the available node count exactly, so a full binary tree of height 11 using precisely 23 nodes exists (the caterpillar shape itself, with no nodes left over that would need to be placed elsewhere).
Step 6: Rule out height 12.
Height 12 would require at least \(2(12) + 1 = 25\) nodes, which exceeds the available 23 nodes, so height 12 is not achievable.
Step 7: Conclusion.
The maximum possible height of a full binary tree with 23 nodes is 11.
Was this answer helpful?
0
0
Top GATE CS Programming and Data Structures Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);
View More Questions
Top GATE CS Trees Questions
- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);Consider the following hierarchical cache system with the following access times:
\[ \begin{array}{|c|c|c|} \hline \textbf{Cache Level} & \textbf{Hit Rate} & \textbf{Access Time} \\ \hline L1 & 90\% & 1 \text{ ns} \\ L2 & 80\% & 10 \text{ ns} \\ L3 & 100\% & 100 \text{ ns} \\ \hline \end{array} \]Find \( T_{avg} \) for hierarchical or simultaneous access.
- Consider a binary tree in which every node has either 0 or 2 children. Let \( N>0 \) be the number of nodes in the tree. The number of nodes that have exactly 2 children is:
What is the output of the following C code?
void foo(int *p, int x) { *p = x; } void main() { int *z; int a = 20, b = 25; z = a; // Incorrect: Should be z = a; foo(z, b); printf("%d", a); }Issue: The statement
z = a;is invalid becauseais an integer, andzis a pointer.
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions