# GATE Questions & Answers of Trees, Binary search trees

## What is the Weightage of Trees, Binary search trees in GATE Exam?

Total 30 Questions have been asked from Trees, Binary search trees topic of Programming and Data Structures subject in previous GATE papers. Average marks 1.57.

The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.

##### Show Answer

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0

##### Show Answer

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ____________ .

##### Show Answer

The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

##### Show Answer

The following function computes $X^Y$ for positive integers X and Y.
int exp(int X, int Y) {
int res = 1, a = X, b = Y;

while ( b != 0 ){
if ( b%2 == 0) { a = a*a; b = b/2; }
else           { res = res*a; b = b-1; }
}
return res;
}
Which one of the following conditions is TRUE before every iteration of the loop?

##### Show Answer

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is ___________.

Note: The height of a tree with a single node is 0.

##### Show Answer

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

##### Show Answer

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

 I. 3, 5, 7, 8, 15, 19, 25 II. 5, 8, 9, 12, 10, 15, 25 III. 2, 7, 10, 8, 14, 16, 20 IV. 4, 6, 7, 9, 18, 20, 25

##### Show Answer

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

##### Show Answer

A binary tree T has 20 leaves. The number of nodes in T having two children is___________

##### Show Answer

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are _______.

##### Show Answer

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

##### Show Answer

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___. ##### Show Answer

Consider the following rooted tree with the vertex labeled P as the root: the order in which the nodes are visited during an in-order traversal of the tree is:

##### Show Answer

Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.

typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
int value=0;
if (tree != NULL)

{
if (tree->leftMostChild == NULL)
value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the

##### Show Answer

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.

int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0;
j = n-1;
do {
k = (i+j)/2;
if (x <= listA[k])
j = k-1;
if (listA[k] <= x)
i = k+1;
}while (i <= j);
if (listA[k] == x)
return(k);
else
return -1;
}

Which one of the following statements about the function ProcessArray is CORRECT?

##### Show Answer

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

##### Show Answer

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root.

int height (treeptr n)
{ if (n == NULL) return -1;
if (n
$\to$ left == NULL)
if (n
$\to$ right == NULL) return 0;
else return
$\overline{)B1}$ ; // Box 1
else { h1 = height (n
$\to$ left);
if (n
$\to$ right == NULL) return (1+h1);
else { h2 = height (n
$\to$ right);
return
$\overline{)B2}$; // Box 2
}
}
}

The appropriate expressions for the two boxes B1 and B2 are

##### Show Answer

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?

##### Show Answer

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

##### Show Answer

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is ##### Show Answer

A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?

##### Show Answer

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,….,n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

##### Show Answer

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

##### Show Answer

Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search

1.   f(int Y, int x) {
2.      int i, j, k;
3.      i = 0; j = 9;
4.      do {
5.          k = (i + j) / 2;
6.          if (Y[k] < x) i = k; else j = k;
7.         } while ((Y[k]! = x) && (i < j));
8.      if (Y [k] == x) print f ("x is in the array");
9.      else print f ("x is not in the array");
10. }

On which of the following contents of Y and x does the program fail?

##### Show Answer

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:

##### Show Answer

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

##### Show Answer

The inorder and preorder traversal 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:

##### Show Answer

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

##### Show Answer

Consider the following C program segment where CellNode represents a node in a binary tree:

struct CellNode {
struct CellNOde *leftChild;
int element;
struct CellNode *rightChild;
};
int GetValue (struct CellNode *ptr) {
int value = 0;
if (ptr != NULL) {
if ((ptr->leftChild == NULL) &&
(ptr->rightChild == NULL))
value = 1;
else
value = value + GetValue(ptr->leftChild)
+ GetValue(ptr->rightChild);
}
return(value);
}

The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is: