1

GATE CSE 2014 Set 3

MCQ (Single Correct Answer)

+2

-0.6

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, rightSibiling;
};
Int Dosomething (treeptr tree)
{
int value =0;
if (tree ! = NULL) {
If (tree -> leftMostchild = = NULL)
value=1;
else
value = Dosomething (tree->leftMostchild);
value = value + Dosometing (tree->rightsibiling);
}
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 2

GATE CSE 2014 Set 3

Numerical

+2

-0

Suppose we have a balanced binary search tree T holding n numbers. We are given two
numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose
there are m such numbers in T. If the tightest upper bound on the time to compute the sum is
O( n

^{a}log^{b}n + m^{c}log^{d}n ), the value of a + 10b + 100c + 1000d is _______.Your input ____

3

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 4

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?

Questions Asked from Trees (Marks 2)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE 2021 Set 1 (2)
GATE CSE 2020 (2)
GATE CSE 2019 (1)
GATE CSE 2016 Set 2 (2)
GATE CSE 2014 Set 2 (1)
GATE CSE 2014 Set 3 (3)
GATE CSE 2012 (1)
GATE CSE 2011 (1)
GATE CSE 2009 (1)
GATE CSE 2008 (5)
GATE CSE 2007 (4)
GATE CSE 2006 (5)
GATE CSE 2005 (6)
GATE CSE 2004 (3)
GATE CSE 2002 (1)
GATE CSE 2000 (1)
GATE CSE 1998 (1)
GATE CSE 1997 (1)
GATE CSE 1996 (2)
GATE CSE 1991 (1)

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages