Let T(n) be the number of different binary search trees on n distinct

1.	Let T(n) be the number of different binary search trees on n distinct elements.Then , where x is(A) n-k+1(B) n-k(C) n-k-1(D) n-k-2
Answer» Answer: (B) Explanation: The idea is to make a key root, put (k-1) keys in one subtree and remaining n-k keys in other subtree. A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties − The left sub-tree of a node has a key less than or equal to its parent node’s key. The right sub-tree of a node has a key greater than to its parent node’s key. Now construction binary search trees from n distinct number- Lets for simplicity consider n distinct numbers as first n natural numbers (starting from 1) If n=1 We have only one possibility, therefore only 1 BST. If n=2 We have 2 possibilities , when smaller number is root and bigger number is the right child or second when the bigger number is root and smaller number as left child. If n=3 We have 5 possibilities. Keeping each number first as root and then arranging the remaining 2 numbers as in case of n=2.

Let T(n) be the number of different binary search trees on n distinct elements.Then , where x is(A) n-k+1(B) n-k(C) n-k-1(D) n-k-2

Answer» Answer: (B)
Explanation: The idea is to make a key root, put (k-1) keys in one subtree and remaining n-k keys in other subtree.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

The left sub-tree of a node has a key less than or equal to its parent node’s key.
The right sub-tree of a node has a key greater than to its parent node’s key.

Now construction binary search trees from n distinct number-
Lets for simplicity consider n distinct numbers as first n natural numbers (starting from 1)
If n=1 We have only one possibility, therefore only 1 BST.
If n=2 We have 2 possibilities , when smaller number is root and bigger number is the right child or second when the bigger number is root and smaller number as left child.

If n=3 We have 5 possibilities. Keeping each number first as root and then arranging the remaining 2 numbers as in case of n=2.

Let T(n) be the number of different binary search trees on n distinct elements.Then , where x is(A) n-k+1(B) n-k(C) n-k-1(D) n-k-2

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment