Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key <= x.key. If y is a node in the right subtree of x, then
y.key >= x.key.

[image]

[image]

Node Size Property: every internal node has at least two children (one key) and at most four children (three keys).

Depth Property: all of the external nodes have the same depth. (The tree is balanced.)

[image]

[image]

mhkim9 edit