1
GATE CSE 2012
MCQ (Single Correct Answer)
+2
-0.6
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 expression for the two boxes B1 and B2 are
A
B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))
B
B1 : (height(n->right)), B2 : (1 + max(h1,h2))
C
B1 : height(n->right), B2 : max(h1,h2)
D
B1 : height(n->right), B2 : max(h1,h2)
2
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
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?
A
0
B
1
C
n!
D
(1/n+1) * 2nCn
3
GATE CSE 2009
MCQ (Single Correct Answer)
+2
-0.6
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.
A
2
B
3
C
4
D
5
4
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
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?
A
O(Logn)
B
O(n)
C
O(nLogn)
D
none of the above, as the tree cannot be uniquely determined.
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP