Question

Which one of these statements about a binary search tree is false?

a. only a leaf node can be deleted from a bst. cross out
b. in a bst, the key in the left child node of a given node n is smaller than the key in n. cross out
c. adding a new key value in a bst always happens at a new leaf node level. cross out
d. in a bst, the key in the right child node of a given node n is larger than the key in n.

Answer 1

The false statement is that only a leaf node can be deleted from a binary search tree. Nodes that are not leaf nodes can also be deleted through a specific process that preserves the BST structure.

Step-by-step explanation:

The statement 'only a leaf node can be deleted from a binary search tree (BST)' is false. A node can be deleted from a BST even if it is not a leaf node. When a node with children is deleted, its replacement can either be the largest value in its left subtree or the smallest value in its right subtree. This ensures that the binary search tree property is maintained. The removal process needs to be performed carefully to maintain the structure of the BST.

It's true that in a BST, the key in the left child node of a given node n is smaller and the key in the right child node of node n is larger than the key in n. Moreover, adding a new key value in a BST does indeed always happen at a new leaf node level. This is part of the definition of a BST and ensures that the binary search property is preserved.