CS224 Assignment 4 Spring 2025 (Total 100 points) due to Canvas before 11:30 pm on 4/7
1. True/False. The leftmost node in a binary search tree will contain the minimum element, while the rightmost node will contain the maximum element.
2. True/False. The below is a valid BST?
3. True/False. The below is a valid BST?
4. For the binary search tree shown below, list the elements in the order generated by InOrder traversal.
A. 1 3 5 6 4 7 12 8 10 B. 1 3 4 5 6 7 8 10 12 C. 7 4 1 3 6 5 8 10 12 D. 1 3 5 6 4 7 12 8 10
E. None of Correct
5. For the binary search tree shown below, list the elements in the order generated by PostOrder traversal.
A. 1 4 3 5 8 9 10 B. 1 4 3 5 10 9 8 C. 3 1 4 5 9 8 10 D. 3 4 5 1 9 10 8 E. None of correct
6. For the binary search tree shown below, list the elements in the order generated by PreOrder traversal.
A. 3 4 6 5 7 9 17 22 20 B. 9 4 5 7 17 20 17 22 9
C. 9 4 3 6 5 7 17 22 20 D. 9 3 6 5 4 7 9 17 22 20 E. None of Correct
7. In a preorder tree walk of the binary search tree below, which number comes immediately before 7? What is the time complexity of a preorder tree walk?
a. 6, O(lg n)
b. 8, O(n)
c. 5, O(lg n)
d. 5, O(n)
e. None of Correct
A. a B. b C. c D. d E. None of Correct
8. Consider the following binary tree (This is not BST):
Use String with bracket representation to represent it. Please select one:
A. 1 ( 2 ( 3 4 5 ) ) 6 (7 11 8 ) ( 12 ( ) 13
B. 1 ( 2 (null ) ( 3 (4) (5) ) ) ( 6 (7 (8) (11) ) ( 12 (null ) (13) ))
C. (1 2 ( 3 (4) 5 ) ) (6 (7) 11 (8 ) ( 12 ( null) 13)
D. 1 (2) (3) (4) 5 ) 6 (7) (11) 8 ) ( 12 (13) ( ) )
E. None of Correct
9. Which ones of the following trees are not binary search trees?
1. only A 2. only B 3. only C 4. only D 5. B and C 6. B and D
7. None of Correct
10. We are looking for the key (k=113) in a BST. Which ones of the following node sequences could not be a valid search path?
(1). 234,76,207,108,111,148,113 (2). 86,192,147,86,145,146,122,113
(3). 45,254,96,124,97,105,113 (4). 124,87,92,123,88,91,113
(5) All are invalid search path
A. Only (1) B. only (2) C. (2) and (4) D. only (3) E. (3) and (4)
F. None of Correct
11. Draw a new binary search tree after removing (45, 12, 1) from the below binary search Tree with no balancing mechanism. Which below picture is a correct after removing (45,12,1)? Please select (1 or 2 or 3 or 4)?
A. 1 B. 2 C. 3 D. 4 E. None of them
12. Consider the tree（This is no a BST） below:
Plus, consider tree walk algorithm (pseudocode) below:
Tree-Walk(T)
q = Queue() // initialize a new queue
q.enqueue(T.root)
while q is not empty:
x = q.dequeue()
print( x.key )
if x.right != Nil: //Nil means null
q.enqueue(x.right)
if x.left != Nil:
q.enqueue(x.left)
End
Which key listing is returned by the above algorithm? Express your answer as comma-separated list of numbers (Ex. 1, 5,3 , ... ). The list of keys (printed out) is:
A. 1,2,6,3,7,12,4,5,8,11,13,9,10 B. 1,6,2,7,3,4,12,11,8,5,10,13,9
C. 4,5,3,2,9,10,8,11,7,13,12,6,1 D. 1,6,2,12,7,3,13,11,8,5,4,10,9
E. None of Correct
13. The binary search tree below has been constructed by repeated calls to insertRecursive(Node root, int value), with keys taken from the following list: ( 3,7,7,8,8,11,13,15,24 ). Which sequences of insertions (see below A/B/C/D) could have yielded the below tree? Check all that apply. Hint, you will start to pick up a value from 13 first.
(1). 13,15,24,8,11,7,7,8,3 (2). 13,15,24,8,3,11,7,8,7 (3). 13,15,24,8,3,11,7,8,7 (4). 13,24,15,11,8,7,3,7,8
A. Only (1) B. Only (2) C. (1) and (2) D. Only (3) E. Only (4) F. None of Correct
14. If Tree-Delete (Tree is BST) is called on the following binary search tree to delete the node with key B, the node with key _________ will be moved to replace the deleted node (B). This will free up one position in the tree that needs to be filled in by another node with key _______.
A. D, E B. C, D C. F, C D. D, C F. None of Correct
15. What is the in-order predecessor and successor of node 15 by using below figure and coding?
A. predecessor is 12 and successor is 33 B. predecessor is 14 and successor is 25
C. predecessor is 14 and successor is 42 D. predecessor is 7 and successor is 33
E. None of Correct
16. When delete (13, 16) function is called, selects the correct step-by-step sequence of recursive calls by using below delete ( ) function, shows exactly how the algorithm to delete Node 16 and to update the tree structure with maintaining the BST properties.
|
|
|
|
A.
1. delete (13, 16)
2. delete (16, 16)
3. delete (14, 16)
4. delete (14, 16)
5. delete (12, 12)
3. delete (16, 16)
Finally, Node 16 was deleted
|
B.
1. delete (13, 16)
2. delete (25, 16)
3. delete (16, 16)
4. minValue (20)
5. delete (20, 18)
3. delete (18, 18)
Finally, Node 18 was deleted
|
|
B.
1. delete (13, 16)
2. delete (25, 16)
3. delete (16, 16)
4. delete (20, 16)
5. delete (18, 18)
3. delete (18, 18)
Finally, Node 18 was deleted
|
C.
1. delete (13, 16)
2. delete (25, 16)
3. delete (16, 20)
4. delete (20, 16)
5. minValue(16, 18)
3. delete (18, 16)
Finally, Node 16 was deleted
|
|
E. None of correct
|
|
17. When search(17, 15) function is called, selects the correct step-by-step sequence of recursive calls by using below search ( ) function, and shows the time complexity of O(?) for search function.
|
A.
search () time complexity of O(n)
1. search (17, 15)
2. search (15, 10)
3. search (13, 15)
4. search (10, 15)
return false
|
B.
search () time complexity of O(n)
1. search (17, 15)
2. search (10, 13)
3. search (13, 15)
4. search (14, 15)
return false
|
|
C.
search () time complexity of O(log n)
1. search (17, 15)
2. search (10, 15)
3. search (13, 15)
4. search (14, 15)
return false
|
D.
search () time complexity of O(n)
1. search (17, 15)
2. search (15, 13)
3. search (13, 15)
4. search (14, 15)
return false
|
|
E. None of Correct
|
|
18. If a binary search tree is not __________, it may be less efficient than a linear structure.
A. complete B. empty C. full D. balanced E. None of the above
19. When a node in an AVL tree becomes unbalanced with a balance factor of +2 and its left child has a balance factor of -1 (see below), which rotation is needed?
a) Right Rotation b) Left Rotation c) Left-Right Rotation d) Right-Left Rotation
20. Given an initially empty AVL tree, insert the following keys in this order: [50, 40, 30, 20, 10]. Which one is correct AVL tree with the correct of balance factor?
|
A.
|
B.
|
|
C.
|
D.
None of Correct
|
