Answer the following questions regarding the following data structures: Which ar

Question

Answer the following questions regarding the following data structures:

Which are valid trees? List all correct answers.

Which are valid binary trees? List all correct answers.

Which are valid binary search trees? List all correct answers.

List the nodes of tree i. above in the order in which a level-order traversal would visit them.

List the nodes of tree i. above in the order in which a pre-order traversal would visit them.

List the nodes of tree i. above in the order in which an in-order traversal would visit them.

List the nodes of tree i. above in the order in which a post-order traversal would visit them.

1. Answer the following questions regarding the following data structures: 1 4 2 vi. 5 17 2 3 4 5 6 29 3.3 3 1 2 5 9 a. Which are valid trees? List all correct answers b. Which are valid binary trees? List all correct answers c. Which are valid binary search trees? List all correct answers d. List the nodes of tree i. above in the order in which a level-order traversal would visit them e. List the nodes of tree i. above in the order in which a pre-order traversal would visit them f. List the nodes of tree i. above in the order in which an in-order traversal would visit them g. List the nodes of tree i. above in the order in which a post-order traversal would visit them

Explanation / Answer

a. Which are valid tree? List all correct answers.

A tree is a graph with no loops. Therefore, i., ii., v., and vi., qualify to be a tree.

b. Which are valid binary trees? List all correct answers.

A tree which has atmost 2 children at each node is said to be binary tree. Therefore, i., ii., and vi., qualify to be binary trees.

c. Which are valid binary search trees? List all correct answers.

A binary tree, in which every left child should be less than or equal to the root, and every right child should be greater than the root is said to be a binary search tree. Therefore, ii., and vi., qualify to be binary search trees.

d. List the nodes of tree i. above in the order in which a level-order traversal would visit them.

A level-ordered traversal is a traversal in which you'll visit all the nodes in the level, before moving to the next level.

Therefore, in tree i., the level ordered traversal of nodes will be: 11, 17, 22, 6, 2, 9, 33.

e. List the nodes of tree i., above in the order in which a pre-order traversal would visit them.

Pre-order traversal is a recursive traversal, such that starting from the root, visit the root, then the left subchild, then the right child. Therefore, in tree i., the pre-order traversal is: 11, 17, 6, 2, 22, 9, 33.

f. List the nodes of tree i., above in the order in which an in-order traversal would visit them.

In-order traversal is a recursive traversal, such that starting from the root, visit the left child, then the root, then the right child. Therfore, in tree i., the in-order traversal is: 6, 17, 2, 11, 9, 22, 33.

g. List the nodes of tree i., above in the order in which a post-order traversal would visit them.

Post-order traversal is a recursive traversal, such that starting from the root, visit the left child, then the right child, then the root. Therefore, in tree i., the post order traversal is: 6, 2, 17, 9, 33, 22, 11.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.