Discrete Mathematics Questions and Answers – Tree Traversal

«
»

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

Answer: b
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.
advertisement

2. An important application of binary tree is ______
a) Huffman coding
b) stack implementation
c) queue implementation
d) traverse a cyclic graph
View Answer

Answer: a
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

Answer: c
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.
advertisement

4. What is the minimum height for a binary search tree with 60 nodes?
a) 1
b) 3
c) 4
d) 2
View Answer

Answer: d
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

Answer: b
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.
advertisement

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

Answer: c
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

Answer: d
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

Answer: a
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

Answer: b
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.
advertisement

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

Answer: b
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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn