binary search tree

a binary search tree is a binary tree that has the following restrictions:

the keys of all the nodes in the left subtree of any given node x is smaller than the key of x
the keys of all the nodes in the right side of the tree are bigger or equal to the key of x

for example the following tree is a binary search tree:

insertion

a new key is always inserted as a leaf. we start from the root, making our way downwards by comparing the new key to the key of the current node to decide which child to move to on each iteration, until we hit a leaf node, then we add the new node as its child