Test on Binary search tree

Question 1: When deleting a node that has only one child, the node's value is replaced by its in-order successor before the node is removed.

A. Yes

B. No

Explanation: When deleting a node with only one child, the study materials state that the node is replaced directly by its single child, and its parent's pointer is updated to point to that child. The in-order successor replacement method is specifically described for deleting a node with two children, not one.

Question 2: The depth of an empty Binary Search Tree is -1.

A. Yes

B. No

Explanation: According to the study materials, the height of an empty tree is -1, while the depth refers to the length of the path from the root to a given node. The root itself has a depth of 0.

Question 3: According to the provided materials, what is the correct sequence of actions when searching for a specific value in a Binary Search Tree (BST)?

A. Begin at the root node and compare the target value with the current node's value.

B. If the target value is less than the current node's value, proceed to the left child; if greater, move to the right child.

C. If the target value is found to be equal to the current node's value, the search is successful.

D. If a null pointer is encountered without finding the value, the search continues by checking parent nodes.

Explanation: The study materials state that to search for a value, one must 'Start at the root and compare the target value with the current node's value.' (Option 0). It also says 'If the target value is less than the current node's value, we move to the left child. If the target value is greater than the current node's value, we move to the right child.' (Option 1). Furthermore, 'If the target value is equal to the current node's value, the search is successful.' (Option 2). Option 3 is incorrect because the materials explicitly state 'If we reach a null pointer (meaning an empty child position) without finding the value, the search fails' and does not mention checking parent nodes for continuation.

Question 4: According to the study materials, when deleting a node that has two children in a Binary Search Tree (BST), which of the following steps are involved?

A. The node is simply removed, and its children are reattached to its parent.

B. The value of the node to be deleted is replaced by its in-order successor or in-order predecessor.

C. The in-order successor (smallest value in the right subtree) or in-order predecessor (largest value in the left subtree) is recursively deleted from its original position.

D. Its single child replaces the node, and the parent's pointer is updated to point to that child.

Explanation: When deleting a node with two children, the study materials state that the node cannot simply be removed without breaking the BST property. Instead, its value is replaced by its in-order successor (the smallest value in its right subtree) or its in-order predecessor (the largest value in its left subtree). After this replacement, the successor or predecessor node is then recursively deleted from its original position, which will be a simpler deletion case (Case 1 or Case 2). Option 0 is incorrect because the node cannot simply be removed. Option 3 describes the process for deleting a node with only one child, not two.

Question 5: Does pre-order traversal include recursively traversing the left subtree?

A. Yes

B. No

Explanation: Pre-order traversal is defined by the steps: 'Visit the current node', 'Recursively traverse the left subtree', and 'Recursively traverse the right subtree'. Therefore, it includes recursively traversing the left subtree.