# Trees · Data Structures · GATE CSE

Start Practice## Marks 1

GATE CSE 2023

Which one of the following sequences when stored in an array at locations $$A[1],....,A[10]$$ forms a max-heap?

GATE CSE 2022

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary h...

GATE CSE 2020

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder traversal of the tree?

GATE CSE 2020

What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?

GATE CSE 2018

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

GATE CSE 2015 Set 1

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

GATE CSE 2015 Set 1

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

GATE CSE 2015 Set 1

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

GATE CSE 2015 Set 2

Consider a complete binary tree where the left and the right sub-trees of the root are max-heaps. The lower bound for the number of operations to conv...

GATE CSE 2015 Set 2

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

GATE CSE 2015 Set 3

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

GATE CSE 2015 Set 3

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

GATE CSE 2014 Set 1

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having ...

GATE CSE 2014 Set 3

Consider the following rooted tree with the vertex labelled P as the root
The order in which the nodes are visited during an in-order traversal of th...

GATE CSE 2011

A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

GATE CSE 2008

Which of the following is TRUE?

GATE CSE 2007

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:

GATE CSE 2007

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

GATE CSE 2006

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored a...

GATE CSE 2006

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the b...

GATE CSE 2005

The numbers 1, 2, ........, n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p node...

GATE CSE 2004

Level order traversal of a rooted tree can be done by starting from the root and performing

GATE CSE 2004

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary sear...

GATE CSE 2003

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an
initially empty binary search tree. The binary search tree uses th...

GATE CSE 2000

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. No...

GATE CSE 1998

Which of the following statements is false?

GATE CSE 1996

Which of the following sequences denotes the post order traversal sequence of the tree of previous question?

GATE CSE 1996

In the balanced binary tree in Fig. given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?
...

GATE CSE 1995

A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:

GATE CSE 1987

It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given.

GATE CSE 1987

If the no of leaves in a tree is not a power of 2,then the tree is not a binary tree.

## Marks 2

GATE CSE 2024 Set 2

You are given a set $V$ of distinct integers. A binary search tree $T$ is created by inserting all elements of $V$ one by one, starting with an empty ...

GATE CSE 2024 Set 1

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

GATE CSE 2023

Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation EXTRACT-MAX(A) ex...

GATE CSE 2023

Consider the C function foo and the binary tree shown.
typedef struct node {
int val;
struct node *left, *right;
} node;
int foo(node *p) {
...

GATE CSE 2021 Set 1

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

GATE CSE 2021 Set 1

Consider the following statements.
S1 : The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S2 : The sequenc...

GATE CSE 2020

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a, b]? Assume that the nu...

GATE CSE 2020

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the...

GATE CSE 2019

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and indepen...

GATE CSE 2016 Set 2

Consider the following $$New-order$$ strategy for traversing a binary tree:
$$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$$ Visit the root;
$$\,\,\,\,\,\,\, \...

GATE CSE 2016 Set 2

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

GATE CSE 2014 Set 3

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

GATE CSE 2014 Set 3

Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftM...

GATE CSE 2014 Set 3

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

GATE CSE 2014 Set 2

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

GATE CSE 2012

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

GATE CSE 2011

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

GATE CSE 2009

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.

GATE CSE 2008

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which.
MBCAFHPYK
KA...

GATE CSE 2008

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 5...

GATE CSE 2008

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 52...

GATE CSE 2008

How many distinct BSTs can be constructed with 3 distinct keys?

GATE CSE 2008

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

GATE CSE 2007

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:

GATE CSE 2007

Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode
{
struct CellNOde *leftChild;
...

GATE CSE 2007

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily ...

GATE CSE 2007

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

GATE CSE 2006

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT b...

GATE CSE 2006

Which of the following sequences of array elements forms a heap?

GATE CSE 2006

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent ...

GATE CSE 2006

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node do...

GATE CSE 2006

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at l...

GATE CSE 2005

Postorder traversal of a given binary search tree T produces the following sequence of keys
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one ...

GATE CSE 2005

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is

GATE CSE 2005

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is ...

GATE CSE 2005

How many distinct binary search trees can be created out of 4 distinct keys?

GATE CSE 2005

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the...

GATE CSE 2005

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8, 5, 3, 2
Tw...

GATE CSE 2004

Consider the following C program segment
struct CellNode{
struct CellNode *leftChild;
int element;
struct CellNode *rightChild;
};
...

GATE CSE 2004

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?
i...

GATE CSE 2004

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of com...

GATE CSE 2002

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

GATE CSE 2000

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tre...

GATE CSE 1998

A complete n-ary tree is one in which every node has O or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves ...

GATE CSE 1997

A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the follow...

GATE CSE 1996

A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of nodes in t...

GATE CSE 1996

A binary search tree is used to locate the number 43. Which of the following
probe sequences are not possible?

GATE CSE 1991

If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ______
...