## Binary-Trees

 Question 1
Consider the following statements:
I. The smallest element in a max-heap is always at a leaf node.
II. The second largest element in a max-heap is always a child of the root node.
III. A max-heap can be constructed from a binary search tree in Θ(n) time.
IV. A binary search tree can be constructed from a max-heap in Θ(n) time.
Which of the above statements are TRUE?
 A I, II and III B II, III and IV C I, III and IV D I, II and IV
Data-Structures       Binary-Trees       GATE 2019       Video-Explanation
Question 1 Explanation:
i) TRUE: The smallest element in heap is always a leaf node but depends upon the graph, it may be left or right side of the graph.
(ii) TRUE: The second smallest element in a heap is always a child of root node. (iii) TRUE: Converting from binary search tree to max heap will take O(n) time as well as O(n) space complexity.
(iv) FALSE: We can’t convert max heap to binary search tree in O(n) time.
 Question 2

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 independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.

 A 5.54 B 1.34 C 4.25 D 3.82
Data-Structures       Binary-Trees       GATE 2019       Video-Explanation
Question 2 Explanation:
There can be 8 paths between any 2 uniformly & independently chosen leaf nodes.
A node can be chosen twice and the path from that node to itself will be zero.
∴ Path 1 = 0
Similarly,
Path 2 = 2
Path 3 = 4
Path 4 = 4
Path 5 = 6
Path 6 = 6
Path 7 = 6
Path 8 = 6
∴ Expected value = Σ Path length × Probability of selecting path
= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8
= 1/4 + 1/1 + 3/1 + 0
= 4 + 1/4
= 17/4
= 4.25
 Question 3

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.
 A 4 and 15 respectively B 3 and 14 respectively C 4 and 14 respectively D 3 and 15 respectively
Engineering-Mathematics       Binary-Trees       GATE 2017 [Set-1]       Video-Explanation
Question 3 Explanation:
T be a Binary Search Tree with 15 nodes.
The height of a tree with single node is 0.
Minimum possible height is when it is a complete binary tree. Maximum possible height is when it is a skewed tree left/right. So the minimum and maximum possible heights of T are: 3 and 14 respectively.
 Question 4

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:

 A 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20 B 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12 C 7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12 D 7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12
Data-Structures       Binary-Trees       GATE 2017 [Set-2]       Video-Explanation
Question 4 Explanation: From these 2 orders, we can say 12 is the root & 8 is the root of left subtree & 16 is the root of right subtree. From 2, 6, 7 we can identify 6 is the root from preorder traversal and from 9, 10 → 9 is root.
From <17, 19, 20>, 19 as root. Hence, 2,7,6,10,9,8 |,15,17,20,19,16 |12 is the post-order traversal.
 Question 5

Consider the following New-order strategy for traversing a binary tree:

• Visit the root;
• Visit the right subtree using New-order;
• Visit the left subtree using New-order;

The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:

 A + - 1 6 7 * 2 ˆ 5 - 3 4 * B - + 1 * 6 7 ˆ 2 - 5 * 3 4 C - + 1 * 7 6 ˆ 2 - 5 * 4 3 D 1 7 6 * + 2 5 4 3 * - ˆ -
Data-Structures       Binary-Trees       GATE 2016 [Set-2]       Video-Explanation
Question 5 Explanation:
New Order strategy: Root, Right, Left.
Given Reverse Polish Notation as:
3 4 * 5 - 2 ^ 6 7 * 1 + -
We know Reverse Polish Notation takes Left, Right, Root. So the expression tree looks like From the tree, we can write the New Order traversal as: Root, Right, Left.
- + 1 * 7 6 ^ 2 - 5 * 4 3
 Question 6

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

 A 19 B 20 C 21 D 22
Data-Structures       Binary-Trees       GATE 2015 [Set-2]
Question 6 Explanation:
Let the number of vertices of a binary tree with "p" leaves be n then the tree has
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e., root of T) of degree 2
(iii) 'n - p - 1' (i.e., interval) vertices of degree 3
(iv) n - 1 edges
∴ By Handshaking theorem,
p × 1 + 1 × 2 + (n - p - 1) × 3 = 2(n - 1)
⇒n = 2p - 1
= 39 as p = 20
∴ n - p = 19 vertices have exactly two children
 Question 7

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

 A 199 B 198 C 197 D 196
Data-Structures       Binary-Trees       GATE 2015 [Set-3]
Question 7 Explanation:
A binary tree T with n leaf nodes have exactly (n - 1) nodes that have exactly two children.
 Question 8

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. 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: (1+ height(n→right)) B2: max(h1,h2)
Data-Structures       Binary-Trees       GATE 2012
Question 8 Explanation: Now, we analyze the code,
The box B1 gets executed when left sub tree of n is NULL & right subtree is not NULL.
In such case, height of n will be the height of the right subtree + 1.
The box B2 gets executed when both left & right subtrees of n are not NULL.
In such case, height of n will be max of heights of left & right subtrees of n+1.
 Question 9

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 Data-Structures       Binary-Trees       GATE 2011
Question 9 Explanation:
Corresponding to each set only 1 binary search tree can be formed because in-order is fixed. only 1 tree possible. If Binary trees would be asked n! possible corresponding to each distinct tree set. Here tree structure is fixed and have only 1 possibility for BST as elements are distinct.
 Question 10

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

 A 0 B 1 C (n-1)/2 D n-1
Data-Structures       Binary-Trees       GATE 2010
Question 10 Explanation:
Given a Binary Tree with n nodes.
Every node has an odd number of descendants.
Also given every node is considered to be its own descendant. ― This is even number of descendants (2), because A is also considered as a descendant. ― This is odd number of descendants (3), A, B, C are descendants here.
Condition satisfied – odd number, but number of nodes in a tree that has exactly one child is 0.
 Question 11

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:

 A 2h−1 B 2h−1 – 1 C 2h+1– 1 D 2h+1
Data-Structures       Binary-Trees       GATE 2007
Question 11 Explanation:
1, 3, 7, 15, 31, ... = 2h+1 - 1
 Question 12

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

 A 1 B 5 C 4 D 3
Data-Structures       Binary-Trees       GATE 2007
Question 12 Explanation:
Total number of binary trees possible for n nodes is C(n) = (2n)!/(n+1)!n! C(n) = (2(3))!/(3+1)!3! = 6×5×4×3×2×1/4×3×2×1×3×2 = 5
Total no. of possible trees is 5. Total = 5
 Question 13

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:

 A d e b f g c a B e d b g f c a C e d b f g c a D d e f g b c a
Data-Structures       Binary-Trees       GATE 2007
Question 13 Explanation:
Inorder: Left root Right
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g Pre order: a b d e c f g
Post order: d e b f g c a
 Question 14

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:```
 A the number of nodes in the tree B the number of internal nodes in the tree C the number of leaf nodes in the tree D the height of the tree
Data-Structures       Binary-Trees       GATE 2007
Question 14 Explanation:
Let take example, So from applying algorithm to above tree we got the final value v=3 which is nothing but no. of leaf nodes.
Note that height of the tree is also 3 but it is not correct because in algorithm the part
if ((ptr → leafchild = = NULL) && (ptr → rightchild = = NULL)) value = 1;
Says that if there is only one node the value is 1 which cannot be height of the tree because the tree with one node has height '0'.
 Question 15

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. 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 15 Explanation:
The binary right skewed tree follows 2n -1 because level 2 value is 7 and level 3 value 15.
 Question 16

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 16 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 17

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 17 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 18

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 18 Explanation: Total 5 binary trees are possible with the preorder C, B, A.
 Question 19

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 19 Explanation:
Option C: (Proper Representation)
 Question 20

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 20 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 21

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 21 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 22

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 23

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 23 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 24

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 24 Explanation: a, b, c are going to unbalance.
 Question 25

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 25 Explanation:
Postorder:-
Left → Right → Root
g c d b f e a
 Question 26

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 26 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 27

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 28

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 29

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 29 Explanation:  Postorder:
11, 12, 10, 16, 19, 18, 20, 15
 Question 30

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
Question 30 Explanation:
AVL Tree all operations(insert, delete and search) will take O(logn) time.
So, In worst case it will take o(n2 log n) time.
 Question 31

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
Question 31 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 32

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 33

The weighted external path length of the binary tree in figure is _____ A 144
Algorithms       Binary-Trees       GATE 1991       Video-Explanation
Question 33 Explanation: Question 34

Consider the binary tree in Figure: (a) What structure is represented by the binary tree?
(b) Give the different steps for deleting the node with key 5 so that the structure is preserved.
(c) Outline a procedure in pseudo-code to delete an arbitrary node from such a binary tree with n nodes that preserves the structure. What is the worst-case time-complexity of your procedure?

 A Theory Explanation.
Data-Structures       Binary-Trees       GATE 1991
 Question 35

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 35 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.
There are 35 questions to complete.

Register Now