- Courses
- Tutorials
- Practice
- Jobs
Top MCQs on Tree Traversal with Interview Question and Answers | DSA Quiz
Question 1
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD). (II) For every edge (u, v) of G, if u is at depth i and v is at depth j in TB, then ∣i − j∣ = 1. Which of the statements above must necessarily be true?
I only
II only
Both I and II
Neither I nor II
Question 2
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
MABCKYFPH
Pick 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
Question 3
a
/ \\
b e
/ \\ /
c d f
/
g
- 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
Question 4
The in-order and pre-order traversal of a binary tree are d b e a f c g and a b d e c f g respectively. The post order traversal of a binary tree is
e d b g f c a
e d b f g c a
d e b f g c a
d e f g b c a
Question 5
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
Question 6
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the reversal ordering on natural numbers i.e. 9 is assumed to be smallest and 0 is assumed to be largest. The in-order traversal of the resultant binary search tree is
9, 8, 6, 4, 2, 3, 0, 1, 5, 7
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 2, 4, 3, 1, 6, 5, 9, 8, 7
9, 8, 7, 6, 5, 4, 3, 2, 1, 0
Question 7
A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by
- x(n-1)+1
- xn-1
- xn+1
- x(n+1)
Question 8
- A tree with 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.
- The maximum number of nodes in a binary tree of height h is (2^(h+1) -1).
Question 9
- 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 (E - V).
- Depth-first search requires O(V^2) time if implemented with an adjacency matrix.
- Depth-first search requires O(V + E) time if implemented with adjacency lists
- None of these
Question 10
- 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
- 7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12
- 7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
- 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20
There are 42 questions to complete.
