Insertion in BST (Complete Implementation)
This chapter will cover the implementation of Binary Search Tree insertion in Java by using the iterative and recursive approaches.
We'll cover the following...
Introduction
There are two techniques to code an Insertion Function:
- Iterative
- Recursive
First, let’s see how Iterative methodology works. The following tree is what we will build once we successfully implement the insertion functionality in Binary Search Tree code.
Insertion Implementation (Iterative)
Explanation
Add function takes an integer value and then traverses the BST tree for a valid position to insert a value. It starts from the root of the tree and traverses the leaf node. Traversing is based on the BST formula, i.e. if the current node’s value is less than key-value, then we will have to find an appropriate position in the right subtree of the current node before we try to find a position in the left subtree.
When we reach the leaf node, ...