Discrete Mathematics Multiple Choice Questions 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: c
Clarification: 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
Answer: d
Clarification: 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
Answer: b
Clarification: 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/-
Answer: c
Clarification: 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)
Answer: d
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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)
Answer: b
Clarification: 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).