GATE CS 2011 Q.29 (CS Q.29): Binary Trees, Binary Search Trees and Balanced Trees

We are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

$n!$

$\frac{1}{n+1} \binom{2n}{n}$

Official answer and solution

Official answer: B
From: Official GATE 2011 answer key

Solution

Use the property that the inorder traversal of any Binary Search Tree produces a uniquely sorted sequence.

Let $S = \{x_1, x_2, \dots, x_n\}$ be a set of $n$ distinct keys sorted in strictly increasing order $x_1 < x_2 < \dots < x_n$ .

In any valid Binary Search Tree (BST), an inorder traversal visits all nodes in strictly increasing order of their key values.

For a given, fixed unlabeled binary tree structure with $n$ nodes, the inorder traversal sequence of tree nodes is fixed and unique.

Therefore, the $k$ -th node visited during the inorder traversal must receive the $k$ -th sorted element $x_k$ for every $k \in \{1, 2, \dots, n\}$ . There is exactly 1 unique valid assignment.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2011 Computer Science and Information Technology (CS)
Question: 29 of 65, printed as CS Q.29
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source