Now that we have seen how to search in a BST, let's think about how to construct a BST. In other words, how is a (key, value) pair inserted into a tree?
Here's the pseudocode for the algorithm to insert a new (key, value) pair (k, v):
Search for k in the BST. If it already exists, return without modifying the tree.
If we don't find a node with key k, then the last node in the search will become the parent P of the new node N.
If k is less than P's key, then N will become P's new left child.
Otherwise (k is greater than P's key) N will become P's new right child.
After the insertion algorithm completes, the BST will maintain the search-tree property!
Note: different BST variants may handle the case of k already existing differently. For example, they may choose to overwrite the value associated with k, or may maintain a list of values for each key.