Exams › GATE › Technical

The maximum number of binary trees that can be formed with three unlabeled nodes is:

1. 1
2. 5
3. 4
4. 3

Correct answer: 5

Solution

The number of distinct binary tree shapes with $n$ unlabeled nodes is the $n$th Catalan number. For $n=3$, the Catalan number is 5, so there are 5 possible binary trees.

Related GATE Technical questions

• A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
• An array \([82, 101, 90, 11, 111, 75, 33, 131, 44, 93]\) is heapified. Which one of the following options represents the first three elements in the heapified array?
• Consider a binary min-heap containing 105 distinct elements. Let \(k\) be the index in the underlying array of the maximum element stored in the heap. The number of possible values of \(k\) is
• Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
• The height of a binary tree is the maximum number of edges in any root-to-leaf path. The maximum number of nodes in a binary tree of height $h$ is:
• The inorder and preorder traversals of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is

⚔️ Practice GATE Technical free + battle 1v1 →