BST Insertion

It is the right time to learn how to insert nodes into the BST.

There are 3 cases:

• The tree is empty;
• An element isn't in the tree;
• An element is already in the tree.

The tree is empty

In this case, an inserted node will be a new root:

• The tree is empty;
• The inserted element becomes a root. The tree is not empty.

An element isn't in the tree

In this case, we need to find the place for an element and then insert it:

• The tree is not empty;
• 11 ≠ 8;
• 11 > 8 – go right;
• 11 ≠ 12;
• 11 < 12 – go left;
• 11 ≠ 10;
• 11 > 10 – go right;
• The next node for comparison is missing. Inserting the element.

An element is in the tree

In this case, we need to be sure that an inserted element is already in the tree not to perform the insertion:

• The tree is not empty;
• 11 ≠ 8;
• 11 > 8 – go right;
• 11 ≠ 12;
• 11 < 12 – go left;
• 11 ≠ 10;
• 11 > 10 – go right;
• Oops! The element is already there. We don’t insert anything!

Well done! Now you know how to insert elements into a binary tree.