Question

Which of these are invariants of a binary search tree:

A. The most recent value inserted is located at the root.
B. The most recent value inserted is a leaf.
C. Root value is larger than all values in the left child.
D. Root value is smaller than all values in the left child.
E. Root value is larger than all values in the right child
F. Root value is smaller than all values in the right child.
G. The left child is not empty (i.e., defined and not null).
H. The right child is not empty (i.e., defined and not null).
I. The left child is a binary search tree.
J. The right child is a binary search tree.
K. I don't know

Answer 1

In a binary search tree, the root is always larger than the values in the left child and smaller than those in the right child. Subtrees of a BST are also BSTs themselves.

Step-by-step explanation:

In a binary search tree (BST), certain properties are always maintained. The root value being larger than all values in the left child and smaller than all values in the right child are two such invariants. These properties are outlined in option C, which states that the root value is larger than all values in the left child, and option F, which asserts that the root value is smaller than all values in the right child.

Additionally, the invariance of the structure of a binary search tree is such that its subtrees must also be binary search trees, as stated in options I and J.