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?
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 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:
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 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:
+ - 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 | |
(n-1)/2 | |
n-1 |
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:
2h−1 | |
2h−1 – 1 | |
2h+1– 1 | |
2h+1
|
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:
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.
log2n | |
n | |
2n+1 | |
2n-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 non-empty 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 2h+1 - 1.
h=2 ⇒ 23 - 1 ⇒ 7

Question 22 |
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?
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 n2 elements into an AVL-tree with n elements initially?
θ(n4)
| |
θ(n2)
| |
θ(n3) | |
θ(n2 log n) |
In question they asked about n2 elements.
So, In worst case it will take o(n2 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 nth 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 = ∑wIw, where Iw is the path length of external node w),≤ n2 always. | |
≥ n log2 n always. | |
Equal to n2 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 pre-order and post-order 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 |
2nCn/n+1 = 6C3/7 = 5
Question 38 |
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
n1 + n2 - 1 | |
n1 - 2 | |
[((n1 + n2)/2)] | |
n2 - 1 |

n1 = 3
n2 = 1
n3 = 1
So, option (B) satisfies.
Question 39 |
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?
2 * n1 – 3 | |
n2 + 2 * n1 – 2 | |
n3 – n2 | |
n2 + n1 – 2 |

n1 = 3
n3 = 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⌋ | |
⌈(i-1)/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
⌊log2 i⌋ | |
⌈log2 (i + 1)⌉ | |
⌊log2 (i + 1)⌋ | |
⌈log2 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 Tree-1 and Tree-2, respectively, will produce the same sequence?
Preorder, Postorder | |
Postorder, Inorder | |
Postorder, Preorder | |
Inorder, Preorder |
→ Post order traverses Left, Right, Root.
→ In-order traverses Left, Root, Right.
Tree-1: Post order: GJIHEFBDCA
Tree-2: In order: GJIHEFBDCA
Question 48 |

+,-,*,a,b,c,d | |
a,-,b,+,c,*,d | |
a,b,c,d,-,*,+ | |
-,a,b,+,*,c,d |

Step-2: The post order sequence is 4526731. The same we have to take it for above constraint.
Step-3: 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 |
log2n 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 non-leaves 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 | |
log2 n nodes | |
2n-1 | |
2n |

Question 52 |
8 | |
15 | |
14 | |
13 |

Question 53 |
30 | |
60 | |
90 | |
None of the above |
n=4. Here, n is number of nodes.
44-2=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 non-leaf 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,non-leaf 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 k-1 | |
2 k -1 | |
2 k-1 -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 h-1 -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 non-leaf (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 bottom-most 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, 2h-1 = 29 = 512.
The nodes with degree 2 are internal nodes 2h-1 - 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*d-e/f |
Inorder→ left,root and right.
a+b*d-c/f
Question 68 |
2h-1 | |
2h+1 | |
2h+1-1 | |
2h+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*4-1
=8-1
=7
Question 77 |
1.7 | |
2.15 | |
3.4 | |
3.8 |

Step-2: Perform optimal merge pattern
0.40, 0.25, 0.15, 0.12, 0.08


Step-4: 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 |
2d – 1 | |
2d + 1 – 1 | |
d + 1 | |
d |
Properties:
→The number of nodes at depth d in a perfect binary tree = 2d
→A perfect binary tree of height h has 2h+1 -1 nodes
→Number of leaf nodes in a perfect binary tree of height h = 2h
→Number of internal nodes in a perfect binary tree of height h = 2h -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 = 2h+1 -1
Question 79 |
In-order : j e n k o p b f a c l g m d h I
Post-order : j n o p k e f b c l m g h i d a
The Pre-order 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 |

Step-2:

Step-3: Final tree is

Step-4: 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) = maxu∈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 |
20 + 21 + ….. 2h | |
20 + 21 + ….. 2h – 1 | |
20 + 21 + ….. 2h + 1 | |
21 + ….. 2h + 1 |
Suppose, in level-3, it have 23=8 nodes.
Question 88 |
256 | |
255 | |
248 | |
None of these |
-- nodes=8
-- Total number of trees=?
Possibility-1: To find total number of trees using nn-2.
= 88-2
= 262144 trees are possible.
Possibility-2: According to given problem, they are using binary tree based on below formula
= 2n -n
= 28 -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 log2n | |
About 2 log2n | |
About n log2n | |
About 2n |
level-1: 1 and 2
level-2: 3 and 6.
[Note: Assume that root starts from level-0]

The height of the binary tree is O(log2n). As per the given constraint, we have to calculate individually of left farthest node and right farthest node height.
=log2n*log2n
=2*log2n or (log2n)2
Question 93 |
2k-1
| |
2k-1 | |
2k | |
2k+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) | |
Ω (n2) |

Question 97 |
1024 | |
210 - 1 | |
1000 | |
None of the above |
→ To find maximum number of nodes in a binary tree of depth using formula is
= 2h+1 -1
= 211 -1
= 2048-1
= 2047

Question 98 |
e = i+n | |
e = i+2n | |
e = 2i+n | |
e = 2n+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. 399-400). 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 option-D is correct.
Question 103 |
|log2 (N+1) | |
N-1 | |
N | |
[log2 (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 sub-tree, and less than or equal to any key stored in the right sub-tree.
Only option A is false
Question 105 |
2L+1 | |
2L | |
2L | |
2L-1 |
Question 106 |
Ceil (log2 (n+1)) | |
1.44 log2n | |
Floor (log2 (n+1)) | |
1.64 log2n |
Maximum: floor(1.44*log2(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, Post-order of above tree will be: ABCFHEGD. Hence, Post-order of above tree will be: ABCFHEGD.
Question 109 |
A full binary tree with n leaves contains
n nodes | |
log2 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 | |
(n-1)
|
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
| |
2-3 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.
LST-6, RST-2 | |
LST-5, RST-3
| |
LST-3, RST-5
| |
LST-2, RST-6
|
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 (n-1)+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(n-1) + 1
log(7-1) + 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