Tree may be designed to allow (or not allow) duplicates
If duplicates are allowed they are inserted left or right. The specific tree spec will dictate if they should be placed left or right (via "less than" or "less than or equal" in the comparison.
If duplicates are not allowed, if a match is found, the new data replaces the old data for the matching node.
If the new data is smaller than the node's data, then we search/insert into the left subtree
Else if the new data is larger than the node's data, then we search/insert into the right subtree
Also see the previous discussion of "Duplicates"
What Are We Comparing?
The simplest approach is to require that all elements are of type Comparable. This approach is limited in that a comparable only supports one sort.
The problem with that solution is that for many objects, we'll want to sort in different ways, e.g. by id, name, and address, etc.
We'll utilize functional programming to add this flexibility.
Key?
In the materials, we'll often see that we search for a given element with a given element. E.g. search for an employee object given an employee object.
Another approach that is more intuitive is to search by a key. Using generics, we define the key to be any type. As an example let's say we have different search trees that support these keys (for an Employee):
A key of type "Long" for an id search
A key of type "String" for an name search
A key of type "String" for an address search
A key of type "Address" for a more dynamic address search (e.g. using state, zip and street address)