Overview and Requirements( Python) For this micro assignment, you are going to d

Question

Overview and Requirements( Python)

For this micro assignment, you are going to download this Jupyter Notebook and answer the following questions. Your answer for a problem should be in a cell immediately after the problem cell. Do not modify the problem cell.

We are going to solve several problems related to trees and their efficiency. This micro assignment includes conceptional questions and programming.

Conceptual Questions

Solve the following problems and justify your answers:

(2 pts) Is the tree full?

(2 pts) Is the tree complete?

(2 pts) What is the tree's height?

List the nodes in the tree in the order they would be visited during a:

(4 pts) Pre-order traversal

(4 pts) Level-order traversal

(4 pts) Post-order traversal

(4 pts) In-order traversal

(2 pts) What is the time complexity to search a full BST?

The following questions refer to the same BST. The operations are cumulative:

(2 pts) Show the BST that would result from inserting the items 35, 20, 30, 50, 45, 60, 18, 25 in this sequence.

(2 pts) Show the BST that would result after removing item 35 (promote in order successor).

(2 pts) Show the BST that would result after removing item 18 (promote in order successor).

(2 pts) How would the trees in the previous problems look differently if we promote in order predecessors instead of successors?

Implementation Question

Write a program that implements and tests an AVL tree remove(item) method. This method accepts an item to remove. If the item is in the tree, the method removes the item, re-balances the tree, and returns True. If the item is not in the tree, False is returned.

Bonus (6 pts)

Read about Huffman coding.

(1 pt) In a Huffman tree, the item with the highest frequency of occurrence will have a code with what trait?

Symbol Code Space a e h i n o r s t

Explanation / Answer

///////////////////////////////////////////////////////////

Is the given tree full?

Ans: Yes the tree is full.

Explanation: A binary tree T is full if each node is either a leaf or has exactly two child nodes.

/////////////////////////////////////////////

Is the given tree complete?

Ans: Yes the tree is complete.

Explanation: A binary tree T is said to be complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

////////////////////////////////////////////////////////////////////

What is the tree's height?

Ans: 3

Explanation: The height of a node is the number of edges from the node to the deepest leaf. The height of a tree is the height of the root. So the height of the given tree is 3. Here root node is * and deepest leaf is X or Y. The number of edges from the * to X is 3.

//////////////////////////////////////////////////////////////

Pre-order traversal

Ans: * A 1 X Y 2 B 3 4

Explanation:

Algorithm for Preorder traversal:

   1. Visit the root.

   2. Traverse the left subtree

   3. Traverse the right subtree

////////////////////////////////////////////////////////

Level-order traversal

Ans: * A B 1 2 3 4 X Y

Explanation: Visit the nodes level by level starting from root node and in each level visit node from left to right.

//////////////////////////////////////////////////////

Post-order traversal

Ans: X Y 1 2 A 3 4 B *

Explanation:

Algorithm for Postorder traversal:

   1. Traverse the left subtree

   2. Traverse the right subtree

   3. Visit the root.

///////////////////////////////

In-order traversal

Ans: X 1 Y A 2 * 3 B 4

Explanation:

Algorithm for Inorder traversal:

   1. Traverse the left subtree

   2. Visit the root.

   3. Traverse the right subtree

/////////////////////////////////////////////////////////////

/*As per Chegg guidelines, if a question of the user contains more than one sub-questions then the expert is supposed to answer the four sub parts. Though I have answered 7 questions here. Experts have time constraints. Hope you understand. :) Please repost the rest to get answer.*/

/*If this helps you, please let me know by giving a positive thumbs up. In case you have any queries, do let me know. I will revert back to you. Thank you!!*/

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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