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

In-order traversal of a binary tree involves visiting the nodes in the following order:

1. Visit the left subtree.
2. Visit the current node.
3. Visit the right subtree.

In your case, we have a rooted tree with the following structure:

• P is the root of the tree.
• P has two children: Q and R.
• Q has one child: S.
• R has three children: T, U, and V.
• U has one child: W.

Step-by-Step In-Order Traversal:

Let's break down the in-order traversal of this tree.

1. Start at the root node P.

   • First, visit the left subtree of P, which is Q.
     • Q has a left subtree, which is S. Visit S (since S has no children).
     • Now visit Q.
     • Q has no right subtree, so we move back up to P.

2. Now visit P.

   • P has a right subtree, which is R.
     • First, visit the left subtree of R, which is T. Visit T (since T has no children).
     • Now visit R.
     • Next, visit the middle child of R, which is U.
       • U has a left subtree, which is W. Visit W (since W has no children).
       • Now visit U.
     • Finally, visit the right child of R, which is V. Visit V (since V has no children).

Final In-Order Traversal Order:

The order in which the nodes are visited during in-order traversal is:

S, Q, P, T, R, W, U, V

This is the in-order traversal of the given tree.

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.