16.2. Inserting Duplicate Values

So, now let us see how to insert a value, inserting a value in a search tree fairly straightforward, there is only one place because, remember that the tree is listed in order will give us a shorted list. So, now after adding this value it must second give us a shorted list, so it is like saying that there was only one place to insert a value in a shorted list. So, is like insertion in a shorted list, except we have to find that correct place in the tree to hang it. So, that when we do this in order traversal, it would be in the correct order when we list it out. And it turns out that basically we have to find out where it should be by searching for it and if it is not present, we add it by this search fields.

Inserting a value into a search tree involves finding the appropriate position based on the ordered nature of the tree. The search tree is structured such that for any given node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. To insert a value, we start from the root and compare the value with the current node. If the value is smaller, we move left; if it is larger, we move right. We continue until we find a position where the new value can be added, ensuring that the tree remains sorted.

Consider a library where books are organized by their titles in alphabetical order. If a new book arrives, the librarian must find the correct spot where the book should go. They start from the first book and move right until they find an empty shelf that is in the correct order. This is just like finding the correct location in a search tree to insert a new value!

For instance, if you want to insert 21, then we will walk down the tree and we will look for the place where we should find 21. So, it is smaller than 52 we go a left, smaller than 37 we go a left, bigger than 16 we go right, and then we find that at 28 there is no value of 21, because there is no left, so since it should be to the left of 28, we add it there.

In the example provided, we are inserting the value '21' into the search tree. We start at the root (52) and determine that 21 is less, so we move left to the node with the value 37. Again, 21 is less than 37, so we move left to 16. Since 21 is greater than 16, we now move right to 28. Here, we find that there is no node to the left of 28; thus, 21 is the perfect candidate to be added as the left child of 28. This maintains the tree's sorted structure.

Imagine you are sorting a stack of playing cards. You have a card '21', and as you hold it, you realize it should come after '16' but before '28'. So as you go through the cards, you find the perfect place to insert '21' to keep everything organized.

Now, if we try to insert a value that is already there, for instance, if my prompt was to insert 91. So, we look for 91 and we find it, so we will interpret the insertion of 91 as something which does not disturb it, because we earlier said we do not want to have duplicate values. So, when we insert, we try to find if the fine fields we insert; if we find it, we do nothing.

When trying to insert a value that already exists in the search tree, the tree structure doesn't allow duplicates. In the case of '91', when we search through the tree, we find that it is already present. Instead of inserting it again, the operation simply concludes without making any changes to the tree structure. This preserves the property of unique values in the search tree.

Think of a classroom where each student has a unique identifier. If a new student tries to register with an ID that is already taken, the school system will simply not allow it. This keeps the list of students unique, just like how the search tree keeps its values unique.

So, this is a very simple recursive way to do this. So first of all, we have a special case which such as that the tree is empty, then we just create a new node and point to that node. If we find it, then we do nothing. If the value is smaller than the value of the current node and if we have no left child, then we actually insert. If we have to go left and we cannot go left, then we create a new node to our left and we make that node point to it by its parents.

The recursive method for inserting values into a search tree works by checking a series of conditions. First, if the tree is empty, we create a new node. If the value to insert is less than the current node's value but there is no left child, we add the new node as the left child. However, if there is a left child, we recursively call the insertion method on the left child to continue searching for the correct insertion point. The same process applies for the right side if the value is greater.

Think of a family tree where each person can have children. If you want to add a new person, you check the first ancestor (the root of the family tree). If the new person's name comes before this ancestor's name, you check the left section; if it’s already occupied, you check that person's children recursively until you find an empty position.

--