GATE 2011 CS (CS1) – Question 39
An unlabelled binary-tree shape has n nodes and n distinct keys are supplied. In how many ways can the keys populate it to make a BST?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) 1
Explanation
Every BST has keys in increasing order under inorder traversal. The fixed shape has one fixed sequence of inorder positions, so assigning the sorted keys to those positions uniquely determines every label. Exactly one assignment works, B. Catalan counts apply when the shape itself can vary.