BinaryTrees
Question 1 
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.4 and 15 respectively  
3 and 14 respectively  
4 and 14 respectively  
3 and 15 respectively 
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 2 
The preorder traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the postorder traversal of this tree is:
2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20  
2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12  
7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12  
7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12 
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 postorder traversal.
Question 3 
Consider the following Neworder strategy for traversing a binary tree:
 Visit the root;
 Visit the right subtree using Neworder;
 Visit the left subtree using Neworder;
The Neworder traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5  2 ˆ 6 7 * 1 +  is given by:
+  1 6 7 * 2 ˆ 5  3 4 *  
 + 1 * 6 7 ˆ 2  5 * 3 4  
 + 1 * 7 6 ˆ 2  5 * 4 3  
1 7 6 * + 2 5 4 3 *  ˆ  
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 4 
19  
20  
21  
22 
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e.., root of T) of degree 2
(iii) 'n p1' (i.e., interval) vertices of degree 3
(iv) n 1 edges
∴ By Handshaking theorem,
p×1+1×2+(np1)×3=2(n1)
⇒n=2p1
=39 as p=20
∴ np=19 vertices have exactly two children
Question 5 
199  
198  
197  
196 
Question 6 
B1: (1+height(n→right)) B2: (1+max(h1,h2))  
B1: (height(n→right)) B2: (1+max(h1,h2))  
B1: height(n→right) B2: max(h1,h2)  
B1: (1+ height(n→right)) B2: max(h1,h2) 
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 7 
0  
1  
n!  
Question 8 
0  
1  
(n1)/2  
n1 
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 9 
I and II are preorder and inorder sequences, respectively  
I and III are preorder and postorder sequences, respectively  
II is the inorder sequence, but nothing more can be said about the other two sequences  
II and III are the preorder and inorder sequences, respectively

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 10 
II and III only  
I and III only  
III and IV only  
III only 
Question 11 
I, II and IV are inorder sequences of three different BSTs  
I is a preorder sequence of some BST with 439 as the root  
II is an inorder sequence of some BST where 121 is the root and 52 is a leaf  
IV is a postorder sequence of some BST with 149 as the root

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 13 
n_{1} = 3
n_{2} = 1
n_{3} = 1
So, option (B) satisfies.
Question 14 
2 * n_{1} – 3  
n_{2} + 2 * n_{1} – 2  
n_{3} – n_{2}  
n_{2} + n_{1} – 2 
n_{1} = 3
n_{3} = 1
So, option (A) satisfies.
Question 15 
2^{h}−1  
2^{h−1} – 1  
2^{h+1}– 1  
2^{h+1}

1,3,7,15,31,...=2^{h+1}  1
Question 16 
1  
5  
4  
3 
Total no. of possible trees is 5.
Total = 5
Question 17 
d e b f g c a
 
e d b g f c a  
e d b f g c a
 
d e f g b c a

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 18 
the number of nodes in the tree
 
the number of internal nodes in the tree
 
the number of leaf nodes in the tree
 
the height of the tree

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 19 
35  
64  
128  
5040 
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35
Question 20 
log_{2}n  
n  
2n+1
 
2^{n}1

Note: Assume level numbers are start with 0.
Question 21 
10  
11  
12  
15 
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 22 
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?
{10, 75, 64, 43, 60, 57, 55}  
{90, 12, 68, 34, 62, 45, 55}  
{9, 85, 47, 68, 43, 57, 55}  
{79, 14, 72, 56, 16, 53, 55} 
Question 23 
⌊i/2⌋  
⌈(i1)/2⌉  
⌈i/2⌉  
⌈i/2⌉  1 
Question 24 
O(n)  
O(log n)  
O(n log n)  
O(n log log n) 
Question 25 
⌊log_{2} i⌋  
⌈log_{2} (i + 1)⌉  
⌊log_{2} (i + 1)⌋  
⌈log_{2} i⌉ 
Question 26 
(i) only  
(ii), (iii)
 
(iii) only
 
(iv) only

(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 27 
The number of leaf nodes in the tree
 
The number of nodes in the tree
 
The number of internal nodes in the tree
 
The height of the tree

→ 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 28 
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
O(log n)  
O(n)  
O(n log log n)  
O(n log n) 
And we know that time complexity for building the heap is O(n)
Question 29 
Theory Explanation is given below. 
Total 5 binary trees are possible with the preorder C, B, A.
Question 30 
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?
(1 2 (4 5 6 7))  
(1 (2 3 4) 5 6) 7)  
(1 (2 3 4) (5 6 7))  
(1 (2 3 NULL) (4 5)) 
(Proper Representation)
Question 31 
LASTIN = LASTPOST  
LASTIN = LASTPRE  
LASTPRE = LASTPOST  
None of the above 
But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.
Question 32 
A tree with a n nodes has (n – 1) edges  
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results  
A complete binary tree with n internal nodes has (n + 1) leaves  
Both B and C 
D: The maximum no. of nodes in a binary tree of height h is 2^{h+1}  1.
h=2 ⇒ 2^{3}  1 ⇒ 7
Question 33 
5 3 1 2 4 7 8 6  
5 3 1 2 6 4 8 7  
5 3 2 4 1 6 7 8  
5 3 1 2 4 7 6 8 
Option D:
Let draw binary search tree for the given sequence,
After traversing through this tree we will get same sequence.
Question 34 
1  
3  
7  
8 
a, b, c are going to unbalance.
Question 35 
f e g c d b a  
g c b d a f e  
g c d b f e a  
f e d g c b a 
Left → Right → Root
g c d b f e a
Question 36 
(4, 7)  
(7, 4)  
(8, 3)  
(3, 8) 
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 38 
Equal to the number of ways of multiplying (n+1) matrices.  
Equal to the number of ways of arranging n out of 2n distinct elements.
 
Equal to n!.
 
Both (A) and (C). 
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 n^{th} catalan number.
Question 39 
≤ n^{2} always.  
≥ nlog_{2} n always.  
Equal to n^{2} always.  
O(n) for some special trees. 
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 × logn
But for skewed tree it will be O(n) only.
So, answer will be (D).
Question 40 
True  
False 
Question 41 
True  
False 
In the above binary tree, no. of leaves is 3, which is not the power of 2. Hence the given statement is false.