In a binary search tree where all the stored values are different, the node holding the largest value cannot have two children.

Question

Quizplus · Accepted Answer

In a binary search tree, values to the left of a node are smaller than the value in the node, and values to the right of the node are larger. Therefore, if the node holding the largest value had two children, there would have to be a larger value in the right subtree, which contradicts the fact that the original node held the largest value. Therefore, the node holding the largest value must have only one child or be a leaf node.

In a Binary Search Tree Where All the Stored Values