This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Tree Traversal”.
1. In preorder traversal of a binary tree the second step is ____________
a) traverse the right subtree
b) traverse the left subtree
c) traverse right subtree and visit the root
d) visit the root
View Answer
Explanation: In a preorder traversal of a binary tree first is to visit the root, second traverse the left subtree of the tree and third traverse the right subtree of the tree.
2. An important application of binary tree is ______
a) Huffman coding
b) stack implementation
c) queue implementation
d) traverse a cyclic graph
View Answer
Explanation: A binary tree is used to sort a list of elements; the inorder traversal will do this automatically. Better tree sorting algorithm will involve balancing the trees. The binary coding, in particular for the Huffman coding is an immediate application of binary trees.
3. From the following code identify the which traversal of a binary tree is this __________
//if node has left child order(node.left) //if node has right child order(node.right) visit(node)
a) Inorder traversal
b) preorder traversal
c) postorder traversal
d) Euler tour traversal
View Answer
Explanation: In a postorder traversal of a binary tree first is to traverse the left subtree, second traverse the right subtree of the tree and third is to visit the node.
4. What is the minimum height for a binary search tree with 60 nodes?
a) 1
b) 3
c) 4
d) 2
View Answer
Explanation: If there are k nodes in a binary tree, maximum height of that tree should be k-1, and minimum height should be floor(log2k). By using the formula, minimum height must be 2 when there are 60 nodes in a tree.
5. From the following code identify the which traversal of a binary tree is this __________
function traversal(node)
{
//Input:root node of the tree
//Output:None
visitLeft(node)
//if node has left child
traversal(node.left)
visit_Below(node)
//if node has right child
traversal(node.right)
visitRight(node)
}a) Inorder traversal
b) Euler Tour traversal
c) Post-order traversal
d) Pre-order Traversal
View Answer
Explanation: The code signifies Euler Tour traversal which is a generic traversal of a binary tree. In this tree traversal we have to walk around the tree and visit each node three times:
1. On the left (pre-order), 2. From below (in-order), 3. On the right (post-order) and Create subtrees for all the nodes.
6. For the expression (7-(4*5))+(9/3) which of the following is the post order tree traversal?
a) *745-93/+
b) 93/+745*-
c) 745*-93/+
d) 74*+593/-
View Answer
Explanation: First build a binary tree for the expression then find out the postorder traversal of that tree and after that the answer will be 745*-93/+.
7. The time complexity of calculating the sum of all leaf nodes in an n-order binary tree is __________
a) O(n2)
b) O(n+1)
c) O(1)
d) O(n)
View Answer
Explanation: The approach is to traverse the binary tree in any fashion and check if the node is the leaf node(child node)or not. After that, add node data to the sum variable. So, after summing up all leaf nodes, the time complexity of the operation should be O(n).
8. An immediate application of a Depth First Search traversal is __________
a) count the number of leaf nodes
b) perform Inorder traversal in easy way
c) count number of nodes
d) implement preorder traversal
View Answer
Explanation: Given an n-ary binary tree, by performing DFS traversal on that tree number of leaf nodes can be calculated and for that we need to maintain an array for the leaf count.
9. Breadth First Search traversal of a binary tree finds its application in __________
a) Cloud computing
b) Peer to peer networks
c) Weighted graph
d) Euler path
View Answer
Explanation: Breadth First Search traversal has diverse applications such as in the peer to peer networks like BitTorrent, BFS traversal is used to find all the neighbour nodes of the network.
10. Worst case complexity of Breadth First Search traversal __________
a) O(n*n)
b) O(nlogn)
c) O(n2 logn)
d) O(n3)
View Answer
Explanation: In an n-ary binary tree, we must have to visit all nodes from an adjacent node and repeat the same for next unvisited nodes. Hence, in worst case the time complexity should be O(nlogn).
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Information Technology MCQs
- Check BCA Books
