Homework Questions: 1. How many bytes are required for the whole binary tree, wh
ID: 3640210 • Letter: H
Question
Homework Questions:1. How many bytes are required for the whole binary tree, when it is used to store the following list: 10, 5, 4, 8, 9. Assume that each pointer occupies 4 bytes and each integer occupies 4 bytes as well. ___________________
2. List the nodes that are visited by the function insert to insert 68 in the binary search tree shown in Figure 11-35 in page 679. Simply use comma with no spaces to write the list in your answer. __________________
3. Following list shows the contents of stack as we run through the non-recursive inorder traversal for the binary search tree shown in Figure 11-35.
50
50,30
50,30,25
...
Complete the remaining steps manually. What is the maximum # of elements stored in the stack during the process? ________________
4. Review all 3 non-recursive traversal algorithms in the book carefully. Which algorithm uses the maximum stack space?
a) pre order
b) in order
c) post order
d) All orders use the stack equally
5. What is the level of node 65 in Figure 11-35 in Page 679? ____________________
6. Consider a binary tree with pre-order sequence M-K-L-P-A-N-D, and in-order sequence L-K-M-A-P-N-D. Which item is in the right child of the root node? _______________________
7. Consider a binary tree with post-order sequence m-k-s-p-q-v-a, and in-order sequence k-m-a-p-s-v-q. Which item is in the left child of the root node?
______________________
8. How many unique binary trees are there that generate M-K-L as the pre-order sequence and K-L-M as the post-order sequence?
______________________
9. Write the pre-order sequence for the binary tree given in Figure 11-37 in page 680. Simply use comma with no spaces to write the list.
______________________
10. Write the post-order sequence for the binary tree given in Figure 11-37 in page 680. Simply use comma with no spaces to write the list.
______________________
11. Write the in-order sequence for the binary tree given in Figure 11-34 in page 678. Simply use comma with no spaces to write the list.
______________________
12. After inserting item 81 into the binary search tree shown in Figure 11-35 in page 679, its parent node's item will be:
______________________
13. After inserting item 49 into the binary search tree shown in Figure 11-35 in page 679, its parent node's item will be:
______________________
Binary Trees for the Homework Questions:
Figure 11-35: Figure 11-34:
50 A
/ /
30 80 B F
/ / /
25 40 55 98 C E G
/ / /
48 52 58 85 110 D
/
45 70 90
/
65 79
/
75
Figure 11-37:
50
/
30 80
/ /
25 40 55
48
Explanation / Answer
1)array of five elements , node 8 have integer and 2 pointers , node 5 one integer 1 pointer, node 4 1 integer , node 9 1 integer 1 pointer , node 10 1 integer 5 integers , 4 pointers = 36 bytes 2) something is wrong with your picture :) ... the way it works : compare with root A thin if smaller go on left else right then F(80) is bigger then 68 go right then 55 is smaller then 68 go right then 58 is smaller then 68 go right then 70 is bigger then 68 go left then 65 is smaller then 68 go right insert to the right of 65 3) sack last in first out , it's hard to read the tree 50 30 25 50 30 50 50 40 50 50 48 45 50 48 50 80 80 55 80 55 52 80 55 80 80 58 80 80 70 80 70 65 80 70 80 79 80 79 75 80 79 80 98 98 85 98 98 90 98 110 so the answer is 3 :) i don't have book :) ... so the rest you can post in different question :) good luck
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.