BinaryTrees
Question 1 
Consider the following statements:
 I. The smallest element in a maxheap is always at a leaf node.
II. The second largest element in a maxheap is always a child of the root node.
III. A maxheap can be constructed from a binary search tree in Θ(n) time.
IV. A binary search tree can be constructed from a maxheap in Θ(n) time.
Which of the above statements are TRUE?
I, II and III  
II, III and IV  
I, III and IV  
I, II and IV 
(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) _____.
5.54  
1.34  
4.25  
3.82 
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.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 4 
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 5 
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 6 
A binary tree T has 20 leaves. The number of nodes in T having two children is _________.
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  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 ____.
199  
198  
197  
196 
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
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 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?
0  
1  
n!  
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?
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 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:
2^{h}−1  
2^{h−1} – 1  
2^{h+1}– 1  
2^{h+1}

1, 3, 7, 15, 31, ... = 2^{h+1}  1
Question 12 
The maximum number of binary trees that can be formed with three unlabeled nodes is:
1  
5  
4  
3 
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:
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 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:
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 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[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.
log_{2}n  
n  
2n+1  
2^{n}1 
Note: Assume level numbers are start with 0.
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
(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 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 nonempty tree is passed as argument is
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 18 
Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.
Theory Explanation is given below. 
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?
(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 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?
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 21 
Which of the following statements is false?
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 22 
A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in preorder and the values are printed out. Which of the following sequences is a valid output?
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 23 
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”?
1  
3  
7  
8 
a, b, c are going to unbalance.
Question 24 
Which of the following sequences denotes the post order traversal sequence of the tree of question 14?
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 25 
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
(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 26 
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?
20, 19, 18, 16, 15, 12, 11, 10  
11, 12, 10, 16, 19, 18, 20, 15
 
10, 11, 12, 15, 16, 18, 19, 20  
19, 16, 18, 20, 11, 12, 10, 15 
Postorder:
11, 12, 10, 16, 19, 18, 20, 15
Question 27 
What is the worst case time complexity of inserting n^{2} elements into an AVLtree with n elements initially?
θ(n^{4})
 
θ(n^{2})
 
θ(n^{3})  
θ(n^{2} log n) 
In question they asked about n^{2} elements.
So, In worst case it will take o(n^{2} log n) time.
Question 28 
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.
θ(n log k)  
θ(log n + k)  
θ(k log n)  
θ(log n) 
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 29 
The weighted external path length of the binary tree in figure is _____
144 
Question 30 
Choose the correct alternatives (More than one may be correct). The number of rooted binary trees with n nodes is,
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 31 
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 = ∑_{w}Iw, where I_{w} is the path length of external node w),≤ n^{2} always.  
≥ n log_{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 × log n
But for skewed tree it will be O(n) only.
So, answer will be (D).
Question 32 
It is possible to construct a binary tree uniquely whose preorder and postorder traversals are given?
True  
False 
Question 33 
If the number of leaves in a tree is not a power of 2, then the tree is not a binary tree.
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.
Question 34 
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 MABCKYFPHPick the true statement from the following.
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 35 
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?
II and III only  
I and III only  
III and IV only  
III only 
Question 36 
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?
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 37 
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?
4  
5  
6  
9 
^{2n}C_{n}/n+1 = ^{6}C_{3}/7 = 5
Question 38 
A binary tree with n > 1 nodes has n_{1}, n_{2} and n_{3} nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n_{3} can be expressed as
n_{1} + n_{2}  1  
n_{1}  2  
[((n_{1} + n_{2})/2)]  
n_{2}  1 
n_{1} = 3
n_{2} = 1
n_{3} = 1
So, option (B) satisfies.
Question 39 
A binary tree with n > 1 nodes has n_{1}, n_{2} and n_{3} 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?
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 40 
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?
35  
64  
128  
5040 
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35
Question 41 
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
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 42 
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 43 
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?
⌊i/2⌋  
⌈(i1)/2⌉  
⌈i/2⌉  
⌈i/2⌉  1 
Question 44 
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
O(n)  
O(log n)  
O(n log n)  
O(n log log n) 
Question 45 
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
⌊log_{2} i⌋  
⌈log_{2} (i + 1)⌉  
⌊log_{2} (i + 1)⌋  
⌈log_{2} i⌉ 
Question 46 
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 47 
Which traversals of Tree1 and Tree2, respectively, will produce the same sequence?
Preorder, Postorder  
Postorder, Inorder  
Postorder, Preorder  
Inorder, Preorder 
→ Post order traverses Left, Right, Root.
→ Inorder traverses Left, Root, Right.
Tree1: Post order: GJIHEFBDCA
Tree2: In order: GJIHEFBDCA
Question 48 
+,,*,a,b,c,d  
a,,b,+,c,*,d  
a,b,c,d,,*,+  
,a,b,+,*,c,d 
Step2: The post order sequence is 4526731. The same we have to take it for above constraint.
Step3: Then the sequence will be ab–cd*+ because 1= +, 2= , 3= *, 4= a, 5=b, 6=c and 7=d.
Question 49 
binary search tree  
AVL tree  
completely balanced tree  
Heap 
Question 50 
log_{2}n nodes  
n+1 nodes  
2n nodes  
2n+1 nodes 
Note: if two leaves having the same parent are removed from the tree, the number of leaves and nonleaves will decrease by 1 because the parent will be a leaf. That means the difference between them is constant. And for a tree having just one node that difference is 1.
Question 51 
n nodes  
log_{2} n nodes  
2n1  
2^{n} 
Question 52 
8  
15  
14  
13 
Question 53 
30  
60  
90  
None of the above 
n=4. Here, n is number of nodes.
4^{42}=16.
Given options are wrong options.
Note: Correct answer is 16
Question 54 
What rotation to make  
if all childs nodes are at same level  
when the last rotation occurred  
if the tree is unbalanced 
Question 55 
log _{2} n nodes  
n+1 nodes  
2n nodes  
2n+1 nodes 
● In a binary tree  a tree where each nonleaf node has exactly two sons  number of leaves is n+1. Total number of nodes is 2n+1.
Full Binary Tree:
In the above tree,nonleaf nodes are 7 so total nodes are 2x7+1=15
Question 56 
postorder  
preorder  
inorder  
none of these 
Pre order: The root node is visited first, then the left subtree and finally the right subtree.
Post order: First we traverse the left subtree, then the right subtree and finally the root node.
Question 57 
Search tree  
Heap  
AVL tree  
B tree 
Question 58 
2 ^{k} +1  
2^{ k1}  
2 ^{k} 1  
2 ^{k1} 1 
For example
The minimum number of nodes 2 ^{2} 1=3
Question 59 
Which of the following data structures is used in level order traversal of a binary tree?
Skip list  
Stack  
Array
 
Queue

Example:
Level order traversal of binary tree.
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.
printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
a) print temp_node>data
b) Enqueue temp_node’s children (first left then right children) to q
c) Dequeue a node from q and assign it’s value to temp_node
Note:
Level order traversal of binary tree is time Complexity is O(n) where n is number of nodes in the binary tree.
Question 60 
2 ^{h}  
2 ^{h1} 1  
2^{ h+1} 1  
2 ^{h+1} 
● The number of leaf nodes l in a perfect binary tree, is l = ( n + 1 )/2 because the number of nonleaf (a.k.a. internal) nodes
● This means that a perfect binary tree with l leaves has n = 2 l − 1 nodes. ● In a balanced full binary tree, h = ⎡ log _{2 }(l)⎤ + 1 = ⎡ log _{2} ((n + 1 )/2)⎤ + 1 = ⎡ log_{ 2} (n + 1 )⎤
● In a perfect full binary tree, l = 2 ^{h} thus n = 2^{ h+1} − 1
● The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is ( n + 1 ) , where only 1 node exists in bottommost level to the far left.
●The number of internal nodes in a complete binary tree of n nodes is ⎣ n/2⎦ .
Question 61 
12  
13  
14  
15 
Question 62 
In a full binary tree of height 10, the number of nodes with degree 0,1, and 2 will be ____,____ and ____ respectively.
Note: Consider height of a tree as the number of nodes in the longest path from root to any leaf node
512, 0, 511
 
512, 1, 510  
511, 0, 512
 
511, 1, 511 
Full binary tree consists of either 0 or 2 childs . So one child to the node is not possible.
The number of nodes with the degree of 1 is 0.
The nodes with degree 0 are leaf nodes, 2^{h1} = 2^{9} = 512.
The nodes with degree 2 are internal nodes 2^{h1}  1 = 511.
Question 63 
Consider an AVL tree constructed by inserting the elements 18, 10, 5, 3, 27, 7, 35, 43, 32 one by one. Which of the following options give the number of comparisons to search the key value 45 in this AVL tree?
5  
4  
3  
2 
Question 64 
5 3 1 2 4 7 8 6  
5 3 1 2 6 4 9 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 65 
Binary tree  
Recursive tree  
Insert sort  
Unitary tree 
Question 66 
Average path length  
Median path length  
Mode path length  
Simple deviation path length 
Question 67 
+*/abdef  
a+bd*ef/  
abdef*/+  
a+b*de/f 
Inorder→ left,root and right.
a+b*dc/f
Question 68 
2^{h}1  
2^{h}+1  
2^{h+1}1  
2^{h+1}+1 
→The height of the binary tree is the longest path from root node to any leaf node in the tree
Question 69 
(n/2) 1  
(n/2) +1  
(n–1) / 2  
(n+1) / 2 
→ The maximum height of the tree will be (n–1) / 2. It is standard property of full binary tree.
Question 70 
dbefacg  
debfagc  
dbefcga  
debfgca 
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 71 
1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2, ?
1  
2  
4  
8 
Question 72 
post – order  
in  order  
pre  order  
linear  order 
Example:
In this traversal method, the left subtree is visited first, then the root and later the right subtree. We should always remember that every node may represent a subtree itself.
Question 73 
1  
3  
7  
8 
a, c, d are going to unbalance.
Question 74 
Divide and conquer technique  
Greedy algorithm  
Back tracking  
Dynamic Programming 
Procedure:
1. Divide: select lower or upper half
2. Conquer: search selected half
3. Combine: None
Recurrence relation : T(n)=T(n/2)+Θ(1)
Using masters theorem,
a=1, b=2, k=0,p=0
T(n)=Θ(logn)
Question 75 
1  
3  
7  
8 
a, c, d are going to unbalance.
Question 76 
n nodes  
log _{2} n nodes  
2n –1 nodes  
2^{ n} nodes 
There are 4 leaf nodes in the above tree.
So, total number of nodes are 2*41
=81
=7
Question 77 
1.7  
2.15  
3.4  
3.8 
Step2: Perform optimal merge pattern
0.40, 0.25, 0.15, 0.12, 0.08
Step4: Multiply with length of the code
= (0.40*1) + (0.25*2) + (0.15*3) + (0.12*4) + (0.08*4)
= 2.15
Question 78 
2^{d} – 1  
2^{d + 1} – 1  
d + 1  
d 
Properties:
→The number of nodes at depth d in a perfect binary tree = 2^{d}
→A perfect binary tree of height h has 2^{h+1} 1 nodes
→Number of leaf nodes in a perfect binary tree of height h = 2^{h}
→Number of internal nodes in a perfect binary tree of height h = 2^{h} 1
→The minimum number of nodes in a binary tree of height h = h+1
→The maximum number of nodes in a binary tree of height h = 2^{h+1} 1
Question 79 
Inorder : j e n k o p b f a c l g m d h I
Postorder : j n o p k e f b c l m g h i d a
The Preorder traversal of the tree shall be
a b f e j k n o p c d g l m h i  
a b c d e f j k n o p g l m h i  
a b e j k n o p f c d g l m h i  
j e n o p k f b c l m g h i d a  
None of the above 
Step2:
Step3: Final tree is
Step4: Preorder traversal is Root,left and right
preorder= a b e j k n p o f d g l c m i h
Note: Given options are wrong. Excluded for evaluation.
Question 80 
Search and Insert Operations  
Search and Delete Operations  
Insert and Delete Operations  
Search, Insert and Delete Operations 
Question 81 
Binary search tree  
AVL tree  
Threaded Binary Tree  
Complete Binary Tree 
→ ALV tree
Question 82 
Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree.
d & h  
c & k  
g, b, c, h, i, m  
c & h 
Eccentricity of a vertex u, is
E(u) = max_{u∈v(G)} d(u, v)
i.e., the maximum distance of a node to other nodes is the eccentricity of that node
Radius: The minimum eccentricity from all the vertices is considered as the radius of the Graph G denoted by r(G).
Here radius of the graph, r(G)=3
Center: If the eccentricity of a graph is equal to its radius, then it is known as the central point of the graph.
And in above graph vertex "h" and " c" have eccentricity equal to the radius of the graph. So vertex h and c are the center of graph.
Hence correct answer is option (D).
Question 83 
ABFCDE  
ADBFEC  
ABDECF  
None of the above 
Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 84 
All items in the left subtree are less than root  
All items in the right subtree are greater than or equal to the root  
Each subtree is itself a binary search tree  
All of the above 
2. All items in the right subtree are greater than or equal to the root
3. Each subtree is itself a binary search tree
Question 85 
Dequeue  
Priority  
Tree  
All of the above 
Priority Queue is like a regular queue or stack data structure, but here each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Tree: A tree is a data structure containing a collection of nodes. Here a node can have any number of children. A node with no child is called as leaf node and a node with 1 or more child is called parent node. Each parent node have a pointer to its children.
Question 86 
ABFCDE  
ADBFEC  
ABDECF  
ABDCEF 
Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 87 
2^{0} + 2^{1} + ….. 2^{h}  
2^{0} + 2^{1 }+ ….. 2^{h – 1}  
2^{0} + 2^{1} + ….. 2^{h + 1}  
2^{1} + ….. 2^{h + 1} 
Suppose, in level3, it have 2^{3}=8 nodes.
Question 88 
256  
255  
248  
None of these 
 nodes=8
 Total number of trees=?
Possibility1: To find total number of trees using n^{n2}.
= 8^{82}
= 262144 trees are possible.
Possibility2: According to given problem, they are using binary tree based on below formula
= 2^{n} n
= 2^{8} 8
= 248
Note: They are not given proper input.
Question 89 
In order : E I C F B G D J H K
Preorder : B C E I F D G H J K
The post order traversal of the above binary tree is
I E F C G J K H D B  
I E F C J G K H D B  
I E F C G K J H D B  
I E F C G J K D B H 
Question 90 
4  
5  
6  
7 
Question 91 
54  
27  
26  
None of the above 
Question 92 
About log_{2}n  
About 2 log_{2}n  
About n log_{2}n  
About 2n 
level1: 1 and 2
level2: 3 and 6.
[Note: Assume that root starts from level0]
The height of the binary tree is O(log_{2}n). As per the given constraint, we have to calculate individually of left farthest node and right farthest node height.
=log_{2}n*log_{2}n
=2*log_{2}n or (log_{2}n)^{2}
Question 93 
2^{k}1
 
2^{k1}  
2^{k}  
2^{k}+1 
→ A Binary Tree is full if every node has 0 or 2 children.
→ In a Full Binary, number of leaf nodes is number of internal nodes plus 1
L = I + 1
Where,
L = Number of leaf nodes,
I = Number of internal nodes.
Question 94 
from leaf to root are non–increasing  
from leaf to root are non–decreasing  
from root to leaf are non–decreasing  
from root to leaf are non–increasing 
Question 95 
100,50,75, 60, 98
 
100, 120, 90, 95, 98  
200,70,100, 95, 98  
75, 150, 90, 80, 98 
1. Left subtree is smaller than his root node
2. Right subtree is greater than or equal to his root
Based on above rules, the search operation will perform
Question 96 
O(log n)  
O(n)  
Ω(n log n)  
Ω (n^{2}) 
Question 97 
1024  
2^{10}  1  
1000  
None of the above 
→ To find maximum number of nodes in a binary tree of depth using formula is
= 2^{h+1} 1
= 2^{11} 1
= 20481
= 2047
Question 98 
e = i+n  
e = i+2n  
e = 2i+n  
e = 2^{n}+i 
→ The root has path length zero and the maximum path length in a tree is called the tree's height.
→ The sum of the path lengths of a tree's internal nodes is called the internal path length and the sum of the path lengths of a tree's external nodes is called the external path length.
External Path Length:
The sum over all external (square) nodes of the lengths of the paths from the root of an extended binary tree to each node. For example, in the tree above, the external path length is 25 (Knuth 1997, pp. 399400). The internal and external path lengths are related by
E = I + 2n,
where n is the number of internal nodes.
Question 99 
6  
42  
132  
256 
Here, n=6
= (2*6)! / (6! * (6+1)!)
= (12)! / (6! * (7)!)
= 479001600 / (720*5040)
= 132
Question 100 
925, 221, 912, 245, 899, 259, 363, 364  
3, 400, 388, 220, 267, 383, 382, 279, 364  
926, 203, 912, 241, 913, 246, 364  
3, 253, 402, 399, 331, 345, 398, 364 
Question 101 
struct TreeNode:
int value
TreeNode leftChild
TreeNode rightChild
function preOrder(T):
if T == null:
return []
else:
return [T.value] + preOrder(T.leftChild) + preOrder(T.rightChild)
function inOrder(T):
if T == null:
return []
else:
return inOrder(T.leftChild) + [T.value] + inOrder(T.rightChild)
function postOrder(T):
if T == null:
return []
else:
return postOrder(T.leftChild) + postOrder(T.rightChild) + [T.value]
For some T the functions inOrder(T) and preOrder(T) return the following:
inOrder(T): [12,10,6,9,7,2,15,5,1,13,4,3,8,14,11]
preOrder(T): [5,2,10,12,9,6,7,15,13,1,3,4,14,8,11]
What does postOrder(T) return?
[12,6,10,7,15,2,9,1,4,13,8,11,14,3,5]  
[11,8,14,4,3,1,13,15,7,6,9,12,10,2,5]  
[11,14,8,3,4,13,1,5,15,2,7,9,6,10,12]  
[12,6,7,9,10,15,2,1,4,8,11,14,3,13,5]  
Cannot be uniquely determined from given information. 
Question 102 
The listing of nodes after applying the preorder traversal over the following binary tree is:
A,B,D,H,I,E,J,K,C,F,G,L  
H,D,I,B,J,E,K,A,L,F,C,G  
H,I,D,J,K,E,B,L,F,G,C,A  
A,B,D,H,I,E,J,K,C,F,L,G 
So optionD is correct.
Question 103 
log_{2} (N+1)  
N1  
N  
[log_{2} (N+1)] 
Question 104 
Which of the following statements about the following binary tree is FALSE
It is a binary serach tree  
It is a complete binary tree  
Nodes ‘J’ and ‘K’ are siblings  
Node ‘B’ is the ancestor of node ‘J’ 
The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left subtree, and less than or equal to any key stored in the right subtree.
Only option A is false
Question 105 
2^{L+1}  
2L  
2^{L }  
2^{L1} 
Question 106 
Ceil (log_{2} (n+1))  
1.44 log_{2}n  
Floor (log_{2} (n+1))  
1.64 log_{2}n 
Maximum: floor(1.44*log_{2}(n+2).328)
Node: Option B is most appropriate among all.
Question 107 
ABCDEFGHI  
FBADCEGIH  
FABCDEGHI  
ABDCEFGIH  
None of the above 
Question 108 
ABCDEFGH  
HFEGABCD  
ABCFHEGD  
AFHBECGD 
Preorder: DCBAGEFH
Hence, Postorder of above tree will be: ABCFHEGD. Hence, Postorder of above tree will be: ABCFHEGD.
Question 109 
A full binary tree with n leaves contains
n nodes  
log_{2} n nodes  
2n  1 nodes
 
2n nodes 
Question 110 
The maximum height of a binary tree with 'n' nodes is ____
(n+n)  
(n+1)
 
n  
(n1)

Question 111 
Consider the following two statements.
1. A binary tree T is full if each node is either a leaf or possesses exactly two child nodes.
2. A binary tree with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.
Which statement is/are TRUE?
Only 2  
Only 1  
1 and 2
 
Neither 1 nor 2

S2 is true. The given definition of complete binary tree is correct.
Question 112 
In ____balance factor of a node is the difference between left subtree and right subtree.
Red Balck tree
 
B+ Tree  
AVL tree
 
23 Tree

Question 113 
The following is the sequence of insertion in a binary search tree.
45, 65, 35, 40, 33, 70, 60, 75, 69How many numbers of nodes in Left Sub Tree(LST) and Right Sub Tree(RST) of root node.
LST6, RST2  
LST5, RST3
 
LST3, RST5
 
LST2, RST6

45, 65, 35, 40, 33, 70, 60, 75, 69
Now let’s draw binary search tree,
So LST contains 3 nodes and RST contains 5 nodes.
Question 114 
Consider the following Inorder and Preorder traversal of a tree
Inorder D B E F A G H C Pre Order A B D E F C G HWhat is the postorder traversal of the same tree?
D F E B H C G A  
D F E B G H C A
 
D F E H B G C A
 
D F E B H G C A

Preorder  A B D E F C G H
Using the Inorder and Preorder we will get the tree as,
Now traversing the tree, we will get postorder traversal as,
D F E B H G C A
Question 115 
Which one from the following is a true statement about Binary trees (BST)?
A BST is the Binary tree in which data in the nodes is ordered in a particular way.
 
The data in any nodes of right subtree of BST must be greater than or equal to the data in the given node.
 
A BST have worst case when the data is already in order.
 
All (1), (2) and (3). 
2. True.
3. True, in this case the tree will be skewed.
Question 116 
log (n+1)1  
log (n)  
log (n1)+1  
log (n)+1 
n=7
So depth is 2.
Now let's check option by option,
A) log(n+1)  1
log(7+1)  1
= 3  1 = 2
B) log n
log 7
= 2・8
C) log(n1) + 1
log(71) + 1
log 6 + 1 = 2.58 + 1
= 3.58
D) log n + 1
log 7 + 1
= 2・8 + 1 = 3.8
Question 117 
3  
4  
6  
5 
(2n)!/n!(n+1)!
So, for n=3,
6!/3!4! = 6×5/3×2 = 5