BinaryTrees
Question 1 
If Tree1 and Tree2 are the trees indicated below :
Which traversals of Tree1 and Tree2, respectively, will produce the same sequence?
Which traversals of Tree1 and Tree2, respectively, will produce the same sequence?
Preorder, Postorder  
Postorder, Inorder  
Postorder, Preorder  
Inorder, Preorder 
Question 1 Explanation:
→ Pre order traverses Root, Left, Right.
→ Post order traverses Left, Right, Root.
→ Inorder traverses Left, Root, Right.
Tree1: Post order: GJIHEFBDCA
Tree2: In order: GJIHEFBDCA
→ Post order traverses Left, Right, Root.
→ Inorder traverses Left, Root, Right.
Tree1: Post order: GJIHEFBDCA
Tree2: In order: GJIHEFBDCA
Question 2 
Consider the following tree
If the post order traversal gives abcd*+ then the label of the nodes 1,2,3,… will be
+,,*,a,b,c,d  
a,,b,+,c,*,d  
a,b,c,d,,*,+  
,a,b,+,*,c,d 
Question 2 Explanation:
Step1: Post order traversals yields from left,right and root.
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.
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 3 
A complete binary tree with the property that the value at each node is as least as large as the values at its children is known as
binary search tree  
AVL tree  
completely balanced tree  
Heap 
Question 3 Explanation:
In a Max. Binary Heap, the key value at each node is as least as large as the values at its children. Similarly in Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap.
Question 4 
A full binary tree with n leaves contains:
n nodes  
log_{2} n nodes  
2n1  
2^{n} 
Question 4 Explanation:
A Binary Tree is full if every node has 0 or 2 children. So, in such case, the binary tree with n leaves contains a total of 2*n1 nodes.
Question 5 
A complete binary tree with n nonleaf nodes contains
log_{2}n nodes  
n+1 nodes  
2n nodes  
2n+1 nodes 
Question 5 Explanation:
→ A binary tree where each nonleaf node has exactly two children. The number of leaves is n+1. Total number of nodes is 2n+1.
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.
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 6 
Which of the following number of nodes can form a full binary tree?
8  
15  
14  
13 
Question 6 Explanation:
A full binary tree is a tree in which every node other than the leaves has two children.
In short, a full binary tree with N leaves contains 2N  1 nodes.
Question 7 
How many different trees are there with four nodes A, B, C and D ?
30  
60  
90  
None of the above 
Question 7 Explanation:
For a given nodes”n” , we can get n^{n2} number of different trees
n=4. Here, n is number of nodes.
4^{42}=16.
Given options are wrong options.
Note: Correct answer is 16
n=4. Here, n is number of nodes.
4^{42}=16.
Given options are wrong options.
Note: Correct answer is 16
Question 8 
A full binary tree with n nonleaf nodes contains
log _{2} n nodes  
n+1 nodes  
2n nodes  
2n+1 nodes 
Question 8 Explanation:
● A full binary tree (sometimes proper binary tree or 2tree) is a tree in which every node other than the leaves has two children
● 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
● 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 9 
A balance factor in AVL tree is used to check
What rotation to make  
if all childs nodes are at same level  
when the last rotation occurred  
if the tree is unbalanced 
Question 9 Explanation:
It is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.
Question 10 
traversing a binary tree first root and then left and right subtree called__ traversalt
postorder  
preorder  
inorder  
none of these 
Question 10 Explanation:
In order: The left subtree is visited first, then the root and later the right subtree.
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.
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 11 
Which of the following need not be a binary tree?
Search tree  
Heap  
AVL tree  
B tree 
Question 11 Explanation:
B trees need not be the binary tree. B trees may have more than 2 children. The order of B tree is maximum number of children a node can have.
Question 12 
The maximum number of nodes in a binary tree of level k, k>=1 is:
2 ^{k} +1  
2^{ k1}  
2 ^{k} 1  
2 ^{k1} 1 
Question 12 Explanation:
The number of nodes is equal to 2^{ k} 1 where k≥1. So the minimum level is 1.
For example
The minimum number of nodes 2 ^{2} 1=3
For example
The minimum number of nodes 2 ^{2} 1=3
Question 13 
Which of the following data structures is used in level order traversal of a binary tree?
Skip list  
Stack  
Array
 
Queue

Question 13 Explanation:
Queue data structures is used in level order traversal of a binary tree.
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.
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 14 
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 
Question 14 Explanation:
→ Height of the full binary tree 2^{h} 1.
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.
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 15 
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 15 Explanation:
Question 16 
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}  
2 ^{h1} 1  
2^{ h+1} 1  
2 ^{h+1} 
Question 16 Explanation:
● The number of nodes n in a full binary tree, is at least n = 2 h + 1 and at most n = 2 ^{h+1} − 1 , where h is the height of the tree. A tree consisting of only a root node has a height of 0.
● 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⎦ .
● 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 17 
The number of possible binary trees with 4 nodes is
12  
13  
14  
15 
Question 17 Explanation:
There is one binary tree with one node. There are two differently shaped trees with two nodes. There are 14 different (shaped) binary trees with four nodes. These different trees are shown below.
Question 18 
A binary search tree contains the values 1,2,3,4,5,6,7 and 8. The tree is traverses 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 9 7  
5 3 2 4 1 6 7 8  
5 3 1 2 4 7 6 8 
Question 18 Explanation:
Preorder traversal yields (Root, left, right)
Option D:
Let draw binary search tree for the given sequence,
After traversing through this tree we will get same sequence.
Option D:
Let draw binary search tree for the given sequence,
After traversing through this tree we will get same sequence.
Question 19 
The figure below represents a
Binary tree  
Recursive tree  
Insert sort  
Unitary tree 
Question 19 Explanation:
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
Question 20 
An important quantitative measure of the complexity of a binary tree is its__. It also provides a measure of the average depth of all nodes in the tree
Average path length  
Median path length  
Mode path length  
Simple deviation path length 
Question 20 Explanation:
The number of decisions or, alternatively, the number of branches traversed, in reaching a node is called the path length or path to the node.
Question 21 
For the following binary tree, in operate the traversal yields the expression
+*/abdef  
a+bd*ef/  
abdef*/+  
a+b*de/f 
Question 21 Explanation:
Here, inoperate the traversal yields the expression means INORDER.
Inorder→ left,root and right.
a+b*dc/f
Inorder→ left,root and right.
a+b*dc/f
Question 22 
A full binary tree with height h has _____ nodes.(Assume leaves at h=0)
2^{h}1  
2^{h}+1  
2^{h+1}1  
2^{h+1}+1 
Question 22 Explanation:
→A full binary tree (sometimes proper binary tree or 2tree) is a tree in which every node other than the leaves has two children.
→The height of the binary tree is the longest path from root node to any leaf node in the tree
→The height of the binary tree is the longest path from root node to any leaf node in the tree
Question 23 
Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be
(n/2) 1  
(n/2) +1  
(n–1) / 2  
(n+1) / 2 
Question 23 Explanation:
→ They are given definition of full binary tree. The full binary tree each node has exactly either zero or two children.
→ The maximum height of the tree will be (n–1) / 2. It is standard property of full binary tree.
→ The maximum height of the tree will be (n–1) / 2. It is standard property of full binary tree.
Question 24 
The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively. The postorder Traversal is __________.
dbefacg  
debfagc  
dbefcga  
debfgca 
Question 24 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
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 25 
What item is at the root after the following sequence of insertions into an empty splay tree :
1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2, ?
1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2, ?
1  
2  
4  
8 
Question 25 Explanation:
A splay tree is a selfbalancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion,
lookup and removal in O(log n) amortized time. For many sequences of nonrandom operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown.
Question 26 
Which traversal techniques lists the nodes of a binary search tree in ascending order ?
post – order  
in  order  
pre  order  
linear  order 
Question 26 Explanation:
Inorder traversal technique in binary search tree will always produce ascending 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.
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 27 
In the balanced binary tree given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g” ?
1  
3  
7  
8 
Question 27 Explanation:
a, c, d are going to unbalance.
Question 28 
Binary search tree is an example of :
Divide and conquer technique  
Greedy algorithm  
Back tracking  
Dynamic Programming 
Question 28 Explanation:
Binary search tree is an example of divide and conquer technique.
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)
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 29 
In the balanced binary tree given below, how many nodes will become unbalanced when a node is inserted as a child of the node ”g”.
1  
3  
7  
8 
Question 29 Explanation:
a, c, d are going to unbalance.
Question 30 
A full binary tree with n leaves contains
n nodes  
log _{2} n nodes  
2n –1 nodes  
2^{ n} nodes 
Question 30 Explanation:
A Binary Tree is full if every node has 0 or 2 children. So, in such case, the binary tree with n leaves contains a total of 2*n1 nodes.
There are 4 leaf nodes in the above tree.
So, total number of nodes are 2*41
=81
=7
There are 4 leaf nodes in the above tree.
So, total number of nodes are 2*41
=81
=7
Question 31 
The minimum number of nodes in a binary tree of depth d (root is at level 0) is
2^{d} – 1  
2^{d + 1} – 1  
d + 1  
d 
Question 31 Explanation:
Binary tree is a tree where each node has at most 2 children nodes.
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
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 32 
Consider the Inorder and Postorder traversals of a tree as given below :
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
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 
Question 32 Explanation:
Step1: Post order traversal is Left, Right and Root according to post order we are dividing into inorder list.
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.
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 33 
The worst case time complexity of AVL tree is better in comparison to binary search tree for
Search and Insert Operations  
Search and Delete Operations  
Insert and Delete Operations  
Search, Insert and Delete Operations 
Question 33 Explanation:
AVL tree is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.
Question 34 
In which tree, for every node the height of its left subtree and right subtree differ almost by one ?
Binary search tree  
AVL tree  
Threaded Binary Tree  
Complete Binary Tree 
Question 34 Explanation:
→ AVL tree is a self balancing tree with height difference at most 1. A balance factor in AVL tree is used to check what rotation to make.
→ ALV tree
→ ALV tree
Question 35 
Consider the tree given below
Using the property of eccentricity of a vertex, find every vertex that is the centre of the given tree.
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 
Question 35 Explanation:
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 36 
The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.
ABFCDE  
ADBFEC  
ABDECF  
None of the above 
Question 36 Explanation:
Post order traversal tree is look like
Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 37 
A binary search tree is a binary tree :
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 
Question 37 Explanation:
Binary search tree properties:
1. All items in the left subtree are less than root
2. All items in the right subtree are greater than or equal to the root
3. Each subtree is itself a binary search tree
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 38 
To represent hierarchical relationship between elements, which data structure is suitable ?
Dequeue  
Priority  
Tree  
All of the above 
Question 38 Explanation:
DoubleEnded Queue is a data structure in which insertion and deletion of data takes place from different ends. The insertion of data takes place from REAR end and deletion of data takes place from FRONT end. It follows FIFO( First In First Out) order for implementation.
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.
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 39 
The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.
ABFCDE  
ADBFEC  
ABDECF  
ABDCEF 
Question 39 Explanation:
Post order traversal tree is look like
Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Postorder: DEBFCA
Inorder: DBEAFC
Preorder: ABDECF
Question 40 
The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to
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} 
Question 40 Explanation:
The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to 2^{0} + 2^{1 }+ ….. 2^{h}. because every phase we are getting 2^{h}.
Suppose, in level3, it have 2^{3}=8 nodes.
Suppose, in level3, it have 2^{3}=8 nodes.
Question 41 
The number of different trees with 8 nodes is
256  
255  
248  
None of these 
Question 41 Explanation:
Given data
 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.
 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 42 
Given a binary tree whose inorder and preorder traversal are given by
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
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 42 Explanation:
Question 43 
A binary tree with 27 nodes has _______ null branches.
54  
27  
26  
None of the above 
Question 44 
In a complete binary tree of n nodes, how far are the two most distant nodes? Assume each edge in the path counts as !
About log_{2}n  
About 2 log_{2}n  
About n log_{2}n  
About 2n 
Question 44 Explanation:
According to binary two most distinct nodes are in
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}
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 45 
In a full binary tree of height k, there are __________ internal nodes.
2^{k}1
 
2^{k1}  
2^{k}  
2^{k}+1 
Question 45 Explanation:
→ In a full binary tree of height k, there are 2k1 internal nodes.
→ 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.
→ 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 46 
A binary tree is said to have heap property if the elements along any path :
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 46 Explanation:
A heap is a complete binary tree. A binary tree is said to have heap property if the elements along any path from root to leaf are non–increasing
Question 47 
Which of the following can be the sequence of nodes examined in a binary search tree while searching for key 98 ?
100,50,75, 60, 98
 
100, 120, 90, 95, 98  
200,70,100, 95, 98  
75, 150, 90, 80, 98 
Question 47 Explanation:
Binary search tree will follow some rules
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
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 48 
The height of a binary tree with ‘n’ nodes, in the worst case is :
O(log n)  
O(n)  
Ω(n log n)  
Ω (n^{2}) 
Question 48 Explanation:
The height of a binary tree with ‘n’ nodes, in the worst case is O(n). Sometimes, it will get left skewed/ right skewed based on given input.
Question 49 
The maximum number of nodes in a binary tree of depth 10 :
1024  
2^{10}  1  
1000  
None of the above 
Question 49 Explanation:
→ The depth of binary tree starts from 0 but not 1.
→ To find maximum number of nodes in a binary tree of depth using formula is
= 2^{h+1} 1
= 2^{11} 1
= 20481
= 2047
→ 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 50 
Consider a full binary tree with n internal nodes, internal path length i, and external path length e. The internal path length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf. Which of the following is correct for the full binary tree?
e = i+n  
e = i+2n  
e = 2i+n  
e = 2^{n}+i 
Question 50 Explanation:
→ A node's path length is the number of links (or branches) required to get back to the root.
→ 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.
→ 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 51 
The number of different binary trees with 6 nodes is ______.
6  
42  
132  
256 
Question 51 Explanation:
Using catalan formula to find the total number of binary trees is (2n)! / (n! * (n+1)!)
Here, n=6
= (2*6)! / (6! * (6+1)!)
= (12)! / (6! * (7)!)
= 479001600 / (720*5040)
= 132
Here, n=6
= (2*6)! / (6! * (6+1)!)
= (12)! / (6! * (7)!)
= 479001600 / (720*5040)
= 132
Question 52 
Suppose that we have numbers between 1 and 1,000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined ?
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 52 Explanation:
There are 52 questions to complete.