Binary-Trees

Question 1

An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n - 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n - 1)/2⌋, ⌊(n - 3)/2⌋, ....., 0. The time required to construct a heap in this manner is

A
O(log n)
B
O(n)
C
O(n log log n)
D
O(n log n)
       Algorithms       Binary-Trees       GATE 2004-IT
Question 1 Explanation: 
The above statement is actually algorithm for building a heap of an input array A.
And we know that time complexity for building the heap is O(n).
Question 2

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?

A
20, 19, 18, 16, 15, 12, 11, 10
B
11, 12, 10, 16, 19, 18, 20, 15
C
10, 11, 12, 15, 16, 18, 19, 20
D
19, 16, 18, 20, 11, 12, 10, 15
       Data-Structures       Binary-Trees       GATE 2020       Video-Explanation
Question 2 Explanation: 


Postorder:
11, 12, 10, 16, 19, 18, 20, 15
Question 3

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

A
θ(n4)
B
θ(n2)
C
θ(n3)
D
θ(n2 log n)
       Data-Structures       Binary-Trees       GATE 2020       Video-Explanation
Question 3 Explanation: 
AVL Tree all operations(insert, delete and search) will take O(logn) time.
In question they asked about n2 elements.
So, In worst case it will take o(n2 log n) time.
Question 4

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 number of reported elements is k.

A
θ(n log k)
B
θ(log n + k)
C
θ(k log n)
D
θ(log n)
       Data-Structures       Binary-Trees       GATE 2020       Video-Explanation
Question 4 Explanation: 
The idea is to traverse the given binary search tree starting from root. For every node being visited, check if this node lies in range, if yes, then add 1 to result and recur for both of its children. If the current node is smaller than the low value of range, then recur for right child, else recur for left child.
Time complexity of the above program is O(h + k) where h is the height of BST and k is the number of nodes in a given range.
Here h is log n, hence O(log n+k).
Question 5

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

A
1
B
3
C
7
D
8
       Data-Structures       Binary-Trees       GATE 1996
Question 5 Explanation: 

a, b, c are going to unbalance.
Question 6

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

A
f e g c d b a
B
g c b d a f e
C
g c d b f e a
D
f e d g c b a
       Data-Structures       Binary-Trees       GATE 1996
Question 6 Explanation: 
Postorder:-
Left → Right → Root
g c d b f e a
Question 7

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 the left subtree and right subtree of the root respectively is

A
(4, 7)
B
(7, 4)
C
(8, 3)
D
(3, 8)
       Data-Structures       Binary-Trees       GATE 1996
Question 7 Explanation: 
50 is the root node in BST.
So greater than 50 will be in right subtree of 50 and less than 50 in left subtree.
So, answer will be (7, 4).
Question 8

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 following sequences is a valid output?

A
5 3 1 2 4 7 8 6
B
5 3 1 2 6 4 8 7
C
5 3 2 4 1 6 7 8
D
5 3 1 2 4 7 6 8
       Data-Structures       Binary-Trees       GATE 1997
Question 8 Explanation: 
Preorder traversal means (Root, left, right)
Option D:
Let draw binary search tree for the given sequence,

After traversing through this tree we will get same sequence.
Question 9

Which of the following statements is false?

A
A tree with a n nodes has (n – 1) edges
B
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results
C
A complete binary tree with n internal nodes has (n + 1) leaves
D
Both B and C
       Data-Structures       Binary-Trees       GATE 1998
Question 9 Explanation: 
A: Tree with n nodes must have (n-1) edges.
D: The maximum no. of nodes in a binary tree of height h is 2h+1 - 1.
h=2 ⇒ 23 - 1 ⇒ 7
Question 10

Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the following sequences:

 Inorder       a f b c d g e
 Postorder     a f c g e d b 
A
Theory Explanation.
       Data-Structures       Binary-Trees       GATE 1998
Question 11

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. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

A
(1 2 (4 5 6 7))
B
(1 (2 3 4) 5 6) 7)
C
(1 (2 3 4) (5 6 7))
D
(1 (2 3 NULL) (4 5))
       Data-Structures       Binary-Trees       GATE 2000
Question 11 Explanation: 
Option C:

(Proper Representation)
Question 12

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

A
LASTIN = LASTPOST
B
LASTIN = LASTPRE
C
LASTPRE = LASTPOST
D
None of the above
       Data-Structures       Binary-Trees       GATE 2000
Question 12 Explanation: 
In full Binary tree LASTIN = LASTPRE.
But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.
Question 13

Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.

A
Theory Explanation is given below.
       Data-Structures       Binary-Trees       GATE 2002
Question 13 Explanation: 

Total 5 binary trees are possible with the preorder C, B, A.
Question 14

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) preorder and postorder     (ii) inorder and postorder
(iii) preorder and inorder     (iv) level order and postorder 
A
(i) only
B
(ii), (iii)
C
(iii) only
D
(iv) only
       Data-Structures       Binary-Trees       GATE 2004
Question 14 Explanation: 
→ We have some combinations such that which can be able to identity a tree
(i) Inorder and Preorder
(ii) Inorder and Postorder
(iii) Inorder and Levelorder
→ And following are do not
(i) Post order and Preorder
(ii) Pre order and Level order
(iii) Post order and Level order
Question 15

Consider the following C program segment

struct CellNode
{
  struct CelINode *leftchild;
  int element;
  struct CelINode *rightChild;
}
 
int Dosomething(struct CelINode *ptr)
{
    int value = 0;
    if (ptr != NULL)
    {
      if (ptr->leftChild != NULL)
        value = 1 + DoSomething(ptr->leftChild);
      if (ptr->rightChild != NULL)
        value = max(value, 1 + DoSomething(ptr->rightChild));
    }
    return (value);
}

The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is

A
The number of leaf nodes in the tree
B
The number of nodes in the tree
C
The number of internal nodes in the tree
D
The height of the tree
       Data-Structures       Binary-Trees       GATE 2004
Question 15 Explanation: 
→ Dosomething ( ) returns the max (height of left child + 1, height right child + 1).
→ So given that pointer to root of tree is passed to DoSomething ( ), it will return height of the tree. It is done when the height of single node is '0'.
Question 16

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 at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.

A
log2n
B
n
C
2n+1
D
2n-1
       Data-Structures       Binary-Trees       GATE 2006
Question 16 Explanation: 
The binary right skewed tree follows 2n -1 because level 2 value is 7 and level 3 value 15.
Note: Assume level numbers are start with 0.
Question 17

What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A, B, C? Draw all these binary trees.

A
Theory Explanation.
       Data-Structures       Binary-Trees       GATE 1995
Question 18

A rooted tree with 12 nodes has its nodes numbered 1 to 12 in pre-order. When the tree is traversed in post-order, the nodes are visited in the order 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1.
Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.

A
Theory Explanation.
       Data-Structures       Binary-Trees       GATE 1994
Question 19

Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has 2 descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.

A
Theory Explanation.
       Data-Structures       Binary-Trees       GATE 1993
Question 20

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 in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?

A
35
B
64
C
128
D
5040
       Data-Structures       Binary-Trees       GATE 2007-IT
Question 20 Explanation: 
To find 60 in BST then there are two possible set i.e., greater than 60 and smaller than 60.
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35
Question 21

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
KAMCBYPFH
MABCKYFPH
Pick the true statement from the following.
A
I and II are preorder and inorder sequences, respectively
B
I and III are preorder and postorder sequences, respectively
C
II is the inorder sequence, but nothing more can be said about the other two sequences
D
II and III are the preorder and inorder sequences, respectively
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 21 Explanation: 
In preorder, root comes at the beginning of the traversal sequence and in post order, root comes at last of the traversal sequence.
So, out of the given sequence only I & II are having such kind of order, i.e., K at the beginning and at the last.
Therefore, II is the preorder and I is postorder and the sequence III will definitely be inorder.
Question 22

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, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

A
II and III only
B
I and III only
C
III and IV only
D
III only
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 22 Explanation: 
Question 23

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, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

Which of the following statements is TRUE?

A
I, II and IV are inorder sequences of three different BSTs
B
I is a preorder sequence of some BST with 439 as the root
C
II is an inorder sequence of some BST where 121 is the root and 52 is a leaf
D
IV is a postorder sequence of some BST with 149 as the root
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 23 Explanation: 
A) Incorrect because I & IV are not in ascending order. (Inorder sequence of BST is in increasing order).
B) False because if 439 is root then it should be first element in preorder.
C) This is correct.
D) False because if 149 is root, then it should be last element in postorder.
Question 24

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, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270

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

A
4
B
5
C
6
D
9
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 24 Explanation: 
Formula:
2nCn/n+1 = 6C3/7 = 5
Question 25

A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n3 can be expressed as

A
n1 + n2 - 1
B
n1 - 2
C
[((n1 + n2)/2)]
D
n2 - 1
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 25 Explanation: 

n1 = 3
n2 = 1
n3 = 1
So, option (B) satisfies.
Question 26

A binary tree with n > 1 nodes has n1, n2 and n3 nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?

A
2 * n1 – 3
B
n2 + 2 * n1 – 2
C
n3 – n2
D
n2 + n1 – 2
       Data-Structures       Binary-Trees       GATE 2008-IT
Question 26 Explanation: 

n1 = 3
n3 = 1
So, option (A) satisfies.
Question 27

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 binary tree is

A
10
B
11
C
12
D
15
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 27 Explanation: 
A node in a binary tree has degree 0, 1, 2.
No. of 1 degree nodes = 5
No. of 2 degree nodes = 10
Total no. of edges = (1*5) + (2*10) = 5 + 20 = 25
So, Total no. of edges = 25 + 1 = 26 (No. of nodes in a tree is 1 more than no. of edges)
Total no. of leaf nodes (node with 0 degree) = 26 - 5 - 10 = 11
Question 28

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 be the sequence of nodes examined?

A
{10, 75, 64, 43, 60, 57, 55}
B
{90, 12, 68, 34, 62, 45, 55}
C
{9, 85, 47, 68, 43, 57, 55}
D
{79, 14, 72, 56, 16, 53, 55}
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 28 Explanation: 
In the binary search tree on right side of parent number, the number should be greater than it. But in option C, after 47, 43 appears. So, this is False.
Question 29

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 of element X[i],i≠0 is?

A
⌊i/2⌋
B
⌈(i-1)/2⌉
C
⌈i/2⌉
D
⌈i/2⌉ - 1
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 29 Explanation: 
If index of array start with 1 then directly divide the ith value by 2 and take floor. If index start with '0' then ⌈i/2⌉ - 1.
Question 30

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 does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

A
O(n)
B
O(log n)
C
O(n log n)
D
O(n log log n)
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 30 Explanation: 
It takes O(log n) to heapify an element of heap.
Question 31

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 level 0, the level of element X[i], i ≠ 0, is

A
⌊log2 i⌋
B
⌈log2 (i + 1)⌉
C
⌊log2 (i + 1)⌋
D
⌈log2 i⌉
       Data-Structures       Binary-Trees       GATE 2006-IT
Question 31 Explanation: 
If the root node is at level 0 then the level of element X[i] is ⌊log2 (i + 1)⌋.
Question 32

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

A
True
B
False
       Data-Structures       Binary-Trees       GATE 1987       Video-Explanation
Question 32 Explanation: 
To construct binary tree uniquely we need either inorder and postorder or inorder and preorder.
Question 33

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

A
True
B
False
       Data-Structures       Binary-Trees       GATE 1987       Video-Explanation
Question 33 Explanation: 

In the above binary tree, no. of leaves is 3, which is not the power of 2. Hence the given statement is false.
Question 34

Choose the correct alternatives (More than one may be correct). The number of rooted binary trees with n nodes is,

A
Equal to the number of ways of multiplying (n+1) matrices.
B
Equal to the number of ways of arranging n out of 2n distinct elements.
C
D
Equal to n!
E
Both (A) and (C).
       Data-Structures       Binary-Trees       GATE 1990       Video-Explanation
Question 34 Explanation: 
No. of rooted binary trees (unlabeled) with n nodes is given by nth catalan number which equals (2nCn)/(n+1)
Here, both options A and C are true as option A corresponds to n multiply operations of (n+1) matrices, the no. of ways for this is again given by the nth catalan number.
Question 35

Choose the correct alternatives (More than one may be correct).

The total external path length, EPL, of a binary tree with n external nodes is, EPL = ∑wIw, where Iw is the path length of external node w),
A
≤ n2 always.
B
≥ n log2 n always.
C
Equal to n2 always.
D
O(n) for some special trees.
       Data-Structures       Binary-Trees       GATE 1990       Video-Explanation
Question 35 Explanation: 
Here the question asked for binary tree.
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).
There are 35 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access