Question 1

Consider the following binary search tree diagram:  If node Y is to be removed, which action should be taken? Use the technique presented in the textbook.
A) Modify the V's left reference to point to X.
B) Modify the V's right reference to point to X.
C) Swap the values in V and X, and modify X's right reference to point to V.
D) Modify V to have a null right pointer.

Accepted Answer

Node Y has a single child node, Node X. In order to remove Node Y, Node V must be modified to point to the child node X instead of Y. Since X is greater than V, the right reference of V should be updated to point to X. So, choice B is the correct action to take.

Question 2

Consider the following binary search tree diagram:  Which nodes will be visited in order to insert the letter B into this tree?
A) H
B) H and D
C) H, D, and F
D) H, D, and A

Accepted Answer

The answer of Consider the following binary search tree diagram:...

Question 3

Which of the following may occur as a result of an add operation, on a non-empty binary search tree?
I a new root is created
II the new node becomes the left child of the root
III the new node has a right child upon insertion
A) I
B) II
C) III
D) II and III

Accepted Answer

The answer of Which of the following may occur as...

Question 4

Consider the following binary search tree diagram:  If node J is to be removed, which node should be copied into its location?
A) M
B) L
C) X
D) N

Accepted Answer

The answer of Consider the following binary search tree diagram:...

Question 5

Consider the following tree diagrams:  Which of the above are binary search trees?
A) I
B) II
C) I and II
D) Neither I nor II

Accepted Answer

The answer of Consider the following tree diagrams:  Which...

Question 6

Consider the following binary search tree diagram:  If node F is to be removed, which action should be taken? Use the technique presented in the textbook.
A) Move C into the right subtree of D.
B) Move C into the left subtree of A.
C) Replace F with D's value and replace D with C's value.
D) Modify D to have a null right reference.

Accepted Answer

The answer of Consider the following binary search tree diagram:...

Question 7

Which of the following statements about a binary search tree is correct?
A) Adding elements that are already sorted will result in a balanced binary search tree.
B) Nodes must be moved when a node is removed from the middle of a subtree.
C) The speed of inserting or removing a node is dependent on the shape of the tree.
D) The speed of inserting or removing a node is dependent on the number of subtrees.

Accepted Answer

The speed of inserting or removing a node in a binary search tree is dependent on the shape of the tree. A well-balanced binary search tree allows for faster insertion and removal operations, while a poorly balanced tree could result in slower operations. Adding elements that are already sorted may result in an unbalanced tree, which would take longer for insertion/removal operations. Nodes do not need to be moved when a node is removed from the middle of a subtree, as the algorithm can simply remove the node and rearrange the tree as necessary. The number of subtrees does not affect the speed of insertion or removal.

Question 8

What does the left node reference of a newly inserted binary search tree node get set to?
A) depends where the node is inserted
B) it gets set to the left child of the new node, if one exists
C) always null
D) it gets set to the left child of the root, if it exists

Accepted Answer

The left node reference of a newly inserted binary search tree node always gets set to null initially. This is because it is unknown where the node will be inserted in relation to the existing nodes in the tree.

Question 9

Consider the following binary search tree diagram:  If node D is to be removed, which action should be taken? Use the technique presented in the textbook.
A) Modify K to point to A as its left child, and modify A to point to F as its right child.
B) Modify K to make its left child null.
C) Swap the values in C and D so that C has A as its left child, then remove the new D node.
D) Modify K to point to F as its left child and modify F to point to A as its left child.

Accepted Answer

The answer of Consider the following binary search tree diagram:...

Question 10

Consider the following tree diagrams:  Which are binary search trees?
A) I
B) II
C) I and II
D) Neither I nor II

Accepted Answer

The answer of Consider the following tree diagrams:  Which...

Question 11

Which of the following sequences of insertions will result in a balanced tree?
I 12 , 7, 25, 6, 9, 13, 44
II 12 , 7, 25, 44, 13, 6, 9
III 12, 25, 44, 13, 6, 9, 7
A) I
B) II
C) I and II
D) I and III

Accepted Answer

The answer of Which of the following sequences of insertions...

Question 12

Consider the following binary search tree diagram:  Which of the following trees represents the correct result after inserting element T? 
A) I
B) II
C) III
D) IV

Accepted Answer

In a binary search tree, all elements on the left of a node should be smaller than the node, and all elements on the right should be greater than the node. After inserting T, the correct result should have T as a leaf node on the left of node P. Only option B satisfies this condition. A is incorrect because T is on the right of node P, while C and D both have T as the right child of node O, violating the binary search tree property.

Question 13

Consider the following binary search tree diagram:  Which of the following trees represents the correct result after inserting element B? 
A) I
B) II
C) III
D) IV

Accepted Answer

The answer of Consider the following binary search tree diagram:...

Question 14

Consider the following binary search tree diagram:  Which nodes will be visited in order to insert the letter E into this tree?
A) H
B) H and D
C) H, D, and F
D) H, D, and A

Accepted Answer

We start at the root node, H, which has a value of G. Since E is greater than G, we move to the right subtree, which brings us to the node with value of D. Since E is greater than D, we move to the right subtree again, which brings us to the node with value of F. Since F does not have a right child, we insert E as its right child. Therefore, nodes H, D, and F will be visited in that order.

Question 15

The nodes in our binary search tree implement the Comparable interface. Which tree operations benefit from this design decision?
I add
II search
III delete
A) I
B) II
C) I and III
D) I, II and III

Accepted Answer

The answer of The nodes in our binary search tree...

Question 16

Locating an element in a balanced binary search tree takes ____ time. A) O(n) B) O(log(n)) C) O(1) D) O(n²)

Accepted Answer

A balanced binary search tree has a maximum height of log(n), where n is the number of elements in the tree. Therefore, the time complexity to locate an element in a balanced binary search tree is O(log(n)).

Question 17

In a binary search tree, where the root node data value = 45, what do we know about the values of all the descendants in the right subtree of the root? A) the root's right child value > 45, but the left child of the root's right child key is < 45 B) some values will be > 45, but there may be a few values < 45 C) approximately half the values are < 45, the other half are > 45 D) all will be > 45

Accepted Answer

In a binary search tree, all values in the right subtree of a node are greater than the value of the node itself. Therefore, all values in the right subtree of the root (whose value is 45) will be greater than 45, making option D the correct choice.

Question 18

A binary search tree is made up of a collection of nodes organized with smaller data values on the left and greater values on the right relative to any node. Which of the following Node references must be instance variables of any implementation of a Node class?
I root
II left
III right
A) I
B) II and III
C) I and II
D) I, II and III

Accepted Answer

All nodes in a binary search tree must have a reference to their parent, their left child, and their right child. Therefore, references to the left and right nodes (II and III) must be instance variables of any implementation of a Node class. The root (I) can be passed around as a parameter, but it is more common to also store a reference to the root as an instance variable for easy access.

Question 19

A binary search tree is made up of a collection of nodes organized with smaller data values on the left and greater values on the right, relative to any node. Which of the following Node references must be instance variables of any implementation of a BinarySearchTree class?
I root
II left
III right
A) I
B) II and III
C) I and II
D) I, II and III

Accepted Answer

The root node reference is necessary for any implementation of a BinarySearchTree class as it is used to access the entire tree. The left and right node references can be local variables within the methods of the class, as they are only used within those specific methods to navigate the tree. Therefore, only the root node reference must be an instance variable.

Question 20

Consider the following binary search tree diagram:  If node M is to be removed, which action should be taken?
A) Replace M with the smallest value in its left subtree.
B) Replace M with the smallest value in its right subtree.
C) Replace M with the largest value in its left subtree.
D) Replace M with the largest value in its right subtree.

Accepted Answer

In a binary search tree, if a node has two child nodes, it cannot be removed directly since it would affect the structure of the tree. One way to remove a node is to replace it with the smallest value in its right subtree since this value is larger than all the values in the left subtree but smaller than all the values in the right subtree, maintaining the ordering property of the binary search tree. Therefore, the best choice is to replace M with the smallest value in its right subtree, which is node P in this case.

Quiz 17: Tree Structures

Consider the following binary search tree diagram: If node Y is to be removed, which action should be taken? Use the technique presented in the textbook.

Consider the following binary search tree diagram: Which nodes will be visited in order to insert the letter B into this tree?

Which of the following may occur as a result of an add operation, on a non-empty binary search tree? I a new root is created II the new node becomes the left child of the root III the new node has a right child upon insertion

Consider the following binary search tree diagram: If node J is to be removed, which node should be copied into its location?

Consider the following tree diagrams: Which of the above are binary search trees?

Consider the following binary search tree diagram: If node F is to be removed, which action should be taken? Use the technique presented in the textbook.

Which of the following statements about a binary search tree is correct?

What does the left node reference of a newly inserted binary search tree node get set to?

Consider the following binary search tree diagram: If node D is to be removed, which action should be taken? Use the technique presented in the textbook.

Consider the following tree diagrams: Which are binary search trees?

Which of the following sequences of insertions will result in a balanced tree? I 12 , 7, 25, 6, 9, 13, 44 II 12 , 7, 25, 44, 13, 6, 9 III 12, 25, 44, 13, 6, 9, 7

Consider the following binary search tree diagram: Which of the following trees represents the correct result after inserting element T?

Consider the following binary search tree diagram: Which of the following trees represents the correct result after inserting element B?

Consider the following binary search tree diagram: Which nodes will be visited in order to insert the letter E into this tree?

The nodes in our binary search tree implement the Comparable interface. Which tree operations benefit from this design decision? I add II search III delete

Locating an element in a balanced binary search tree takes ____ time.

In a binary search tree, where the root node data value = 45, what do we know about the values of all the descendants in the right subtree of the root?

A binary search tree is made up of a collection of nodes organized with smaller data values on the left and greater values on the right relative to any node. Which of the following Node references must be instance variables of any implementation of a Node class? I root II left III right

Consider the following binary search tree diagram: If node M is to be removed, which action should be taken?