Questions & Answers of Trees, Binary search trees

Question No. 6

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

Question No. 20

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

Question No. 136

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:

Question No. 145

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?

Question No. 150

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.

Question No. 15

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

Question No. 17

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

Question No. 35

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

Question No. 123

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

Question No. 221

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

Question No. 227

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

Question No. 149

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 ___.

Question No. 222

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:

Question No. 251

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

Question No. 252

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?

Question No. 43

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?

Question No. 47

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
left == NULL)
      if (n
right == NULL) return 0;
      else return
B1 ; // Box 1
  else { h1 = height (n
left);
            if (n
right == NULL) return (1+h1);
            else { h2 = height (n
right);
                      return
B2; // Box 2
                  }
       }
}

The appropriate expressions for the two boxes B1 and B2 are

Question No. 29

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?

Question No. 37

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.

Question No. 19

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

Question No. 41

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?

Question No. 46

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?

Question No. 47

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

Question No. 84

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

1.   f(int Y[10], 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?

Question No. 12

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:

Question No. 13

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

Question No. 39

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:

Question No. 43

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?

Question No. 46

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: