Test: Trees - 2 - Computer Science Engineering (CSE) MCQ

If a tree is not empty, height of tree is
MAX(Height of Left Subtree, Height of Right Subtree) + 1

The order of inorder traversal is
LEFT ROOT RIGHT

The order of preorder traversal is
ROOT LEFT RIGHT

The order of postorder traversal is
LEFT RIGHT ROOT

In all three traversals, LEFT is traversed before RIGHT

Below is the given tree.

                              a
                           /    \
                        /          \
                      b             c
                   /   \          /   \
                 /       \      /       \
               d         e    f          g

Breadth first search visits all the neighbors first and then deepens into each neighbor one by one. The level order traversal of the tree also visits nodes on the current level and then goes to the next level.

It is given that the given tree is complete binary tree. For a complete binary tree, the last visited node will always be same for inorder and preorder traversal. None of the above is true even for a complete binary tree.

The option (a) is incorrect because the last node visited in Inorder traversal is right child and last node visited in Postorder traversal is root.

The option (c) is incorrect because the last node visited in Preorder traversal is right child and last node visited in Postorder traversal is root.

For option (b), see the following counter example. Thanks to Hunaif Muhammed for providing the correct explanation.

     1
   /    \
  2      3
 / \    /
4   5  6  

Inorder traversal is 4 2 5 1 6 3
Preorder traversal is 1 2 4 5 3 6

Algorithm Inorder(tree) - Use of Recursion
Steps:
1. Traverse the left subtree, 
   i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, 
   i.e., call Inorder(right-subtree)

Understanding this algorithm requires the basic 
understanding of Recursion

Therefore, We begin in the above tree with root as
the starting point, which is P.

# Step 1( for node P) :
Traverse the left subtree of node or root P.
So we have node Q on left of P.

-> Step 1( for node Q)
Traverse the left subtree of node Q.
So we have node S on left of Q.

* Step 1 (for node S)
Now again traverse the left subtree of node S which is 
NULL here.

* Step 2(for node S)
Visit the node S, i.e print node S as the 1st element of 
inorder traversal.

* Step 3(for node S)
Traverse the right subtree of node S.
Which is NULL here.

Now move up in the tree to Q which is parent
of S.( Recursion, function of Q called for function of S).
Hence we go back to Q.

-> Step 2( for node Q):
Visit the node Q, i.e print node Q as the 2nd
element of inorder traversal.

-> Step 3 (for node Q)
Traverse the right subtree of node Q.
Which is NULL here.

Now move up in the tree to P which is parent
of Q.( Recursion, function of P called for function of Q).
Hence we go back to P.

# Step 2(for node P)
Visit the node P, i.e print node S as the 3rd
element of inorder traversal.

# Step 3 (for node P)
Traverse the right subtree of node P.
Node R is at the right of P.

Till now we have printed SQP as the inorder of the tree. 
Similarly other elements can be obtained by traversing 
the right subtree of P.

The final correct order of Inorder traversal would 
be SQPTRWUV.

Here, we consider each and every option to check whether it is true or false.

1) Preorder and postorder

 

Postorder is BA

It shows that preorder and postorder can’t identify a tree uniquely.

2) Inorder and postorder define a tree uniquely

3) Preorder and Inorder also define a tree uniquely

4) Levelorder and postorder can’t define a tree uniquely. For the above example,

Level order is AB

Postorder is BA

Binary Search Tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.
  There must be no duplicate nodes.

So let us say n=10, p=4. According to BST property the root must be 10-4=6 (considering all unique elements in BST)
And according to BST insertion, root is the first element to be inserted in a BST.
Therefore, the answer is (n-p).

As here we want subset of edges that connects all the vertices and has minimum total weight i.e. Minimum Spanning Tree
Option A – includes cycle, so may or may not connect all edges.
Option B – has no relevance to this question.
Option C – includes cycle, so may or may not connect all edges.

There are two set of values, smaller than 60 and greater than 60. Smaller values 10, 20, 40 and 50 are visited, means they are visited in order. Similarly, 90, 80 and 70 are visited in order.
= 7!/(4!3!)
= 35

1: abef->c or g should be covered
4: adbc->e or f should be covered
2: abefcgd correct
3: adgebcf correct

In a depth-first traversal of a graph G with V vertices, E edges are marked as tree edges. The number of connected components in G is (V – E).
Only option (A) is false.

Since given tree is binary tree, so inorder traversal will be always sorted order, i.e., 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20.
Now we can draw that binary search tree using given postorder and inorder traversal. Final tree will be:

 

Therefore, preorder travesal will be : 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20.
Option (D) is correct.

There are four types of edges can yield in DFS. These are tree, forward, back, and cross edges. In undirected connected graph, forward and back egdes are the same thing. A cross edge in a graph is an edge that goes from a vertex v to another vertex u such that u is neither an ancestor nor descendant of v. Therefore, cross edge is not possible in undirected graph.
So, statement (I) is correct.

For statement (II) take counterexample of complete graph of three vertices, i.e., K3 with XYZ, where X is source and Y and Z are in same level. Also,there is an edge between vertices Y and Z, i.e., |i-j| = 0 ≠ 1 in BFS. So, statement became false.

Option (A) is correct.

Inorder traversal of a binary search tree always produces the keys in increasing order. In this question Reverse ordering of natural numbers are used i.e. 9 is assumed to be the smallest and 0 to be the largest. So the sequence in increasing order will be 9, 8, 7, 6, 5, 4, 3, 2, 1, 0.
So, option (D) is correct.

Postorder traversal of the given binary tree will give the following sequence: 4 5 2 6 7 3 1.
Now comparing the sequence with a b – c d * + we get 1 = +, 2 = -, 3 = *, 4 = a, 5 = b, 6 = c and 7 = d.
So, option (A) is correct.

We can write the prefix form of the expression as:
(a + (b − c))* ((d − e) / (f + g − h))
= (a + (- b c)) * ((- d e) / ( + f g – h))
= (+ a – b c) * ((- d e) / (- + f g h)
= (+ a – b c) * (/ – d e – + f g h)
= * + a – b c / – d e – + f g h

Inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively.
From preorder(Parent left right) and inorder ( left parent right) we can easily find post order.
From preorder(a(bdecfg)), it is clear that a is parent node(root node), Now we will look for left subttree in inorder traversal i.e. dbe and fcg.
To find root node and left subtree and right subtree of these subtree we will do the same process as above:
Now see this scenario in graph:

Now from above tree we can easily find out the post order(left right parent):
i.e. debfgca.
So, option (D) is correct.

The Inorder traversal of the tree can be seen as:

 

So, the preorder traversal of the following tree is ABFGCDE.

Option (B) is correct.

The numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree with the usual ordering on natural numbers. The inorder sequence of such a binary search tree always yields to the numbers arranged in ascending order.
So, option (C) is correct.