GATE CSE 2026 | Set 1 | Question: 23

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)

Comments

be careful full bt (0 or 2 child)  not complete bt

---

must care full with Definion of Perfect and full and Complete ...dont confuse

full==all nodes have either 0 child or 2 child ..

in question they ask Max height ..So we try increse height as much posiible that meas we try fit minmum posible nodes at every level

 so each step make one node has zero child and another must have 2child (because if both are 0 Child then tree cant grow ) so

this method gives excpet 1st LEVEL i.e root each level we have 2 ...1+11X2=23

 height is =11 not 12 (The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree)

---

Given:

Full binary tree = Every node has either 0 or 2 children
Max of FBT is possible only when skewed
In a skewed structure Height (defined on terms of edges) = No of Internal nodes
So finding no of internal nodes provides us the answer
 

Total Nodes = No of internal nodes * 2 + 1

23 = I * 2 + 1
22 = I * 2
22/2 = I
I = 11

 

---

FULL BINARY TREE:
Min height : \(N = 2^{h+1} - 1\) nodes
Max height: \(N = 2h + 1\)  nodes

Answer 1

we know that for  any binary tree:

total number of nodes $n$= internal nodes $(I)$+ leaf node $( L)$

In a Full Binary Tree, the number of leaves is always one more than the internal nodes:$L=I+1$

Substitute $L$ into the total nodes equation: 

$n = I + (I + 1) = 2I + 1$

now put $n = 23$: 

$23 = 2I + 1 \implies 22 = 2I \implies I = 11$.

To get the maximum height, we should arrange these$11$ internal nodes in a single path (skew tree). Each internal node then contributes exactly 1 edge to the height.Therefore, Max Height = Number of Internal Nodes = 11.

Answer 2

Full binary tree : Every node has either 0 or 2 children.

 

Asked for max height for 23 nodes.

 

In exam i drawn this and made the answer without any formula, ofcourse in less than 1 min hope this helps to build your intuition.

(start first node with count 1, just count the skewed lines it will be 11.)

Answer 3

A full binary tree is a binary tree with either zero or two child nodes for each node.

Remove the root and then the problem boils down to make groups of $2$ with $n-1$ elemets, which will be  $\frac{(n-1)}{2}$.

So ans will be $11$.

I don't know why in the exam I thought full BT = complete BT and answered $4$:)

Comments

Yep I did same and answered 4 T_T

---

same

---

i remebered that dull binary tree has zero child or 2 child so i made a tree but forgot to maximise it by making it skewed , altho i had done a question like this, lesson learnt but at what cost, till now i lost around 6 marks , when i am solving it jhut se but exam mein kya ho gaya bhai, i was not paniking but it was like ki in some question i used all my mental power and was exhausted mentally so tublelight jal nhi rhi thi, alto i gave 15+ mocks

---

same bhai

Answer 4

 

Answer 5

For a full binary tree:

• Every node has either 0 or 2 children
• Maximum height occurs when the tree is as “skewed” as possible while still remaining full.

 

A full binary tree with height h has:

Minimum nodes = 2h+1

(because each internal node contributes exactly one extra leaf)

 

Given:

                         2h+1=23

                         2h=22 

                         h=11

So the maximum possible height is:

11