GATE 2016 CS (CS2) – Question 50
How many insertion orders of 1,2,3,4,5,6,7 give a binary search tree of height six? A single-node tree has height zero.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 64.0 to 64.0
Explanation
Seven nodes and height six force a single chain. At each insertion except the last, choose the minimum or maximum remaining key; any interior choice would put future keys on both sides and break the chain. There are two choices for six positions, then one final key: $2^6=64$.