First let me introduce what is a binary tree.
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
Create a node class
Create a BinarySearchTree class
Adding node to the BSTree
Create a method addNode taking the data to be input
new node is created
set current reference to the root node
create another BSTNOde type reference named parent
If there is no root already root will set to the new node with the data and return
give the reference parent to the root node
then check the value of the new node whether it is lesser than the current.data
if yes then set current to the left child
check if it is null
its not null
then end the first iteration of the while loop and check the above conditions again
here now, lets consider the new node that we are going to add is consists of value 33
so from the next iteration goes as follows
when line 133 execute, it points the parent to current
then check the if conditions
here executes else
and set current to the rightChild of the current
end up the second iteration.
and begin the third iteration.
again parent is set to the current position.
then check 33 is lesser or greater than current.data
33 is lesser so if statement executes to set current to the current.leftChild which is has no value.
Then only executes the line 117 the nested if condition checks whether current is null or not.
yes it is null, so then it assigns new node n to the currents position where it can denote as parent’s left child