## Insertion of a Node in Binary Search Tree

Binary search tree having two characteristics:
(1) All the nodes in a left sub tree having values less then root node.
(2) All the nodes in a right sub tree having values greater then root node.
Suppose we want to construct binary search tree for following set of data:
45 68 35 42 15 64 78

Step 1: First element is 45 so it is inserted as a root node of the tree. Step 2: Now we have to insert 68. First we compare 68 with the root node which is 45. Since the value of 68 is greater then 45 so it is inserted to the right of the root node. Step 3: Now we have to insert 35. First we compare 35 with the root node which is 45. Since the value of 35 is less then 45 so it is inserted to the left of the root node. Step 4: Now we have to insert 42. First we compare 42 with the root node which is 45. Since the value of 42 is less then 45 so it is inserted to the left of the root node. But the root node has already one left node 35. So now we compare 42 with 35. Since the value of 42 is greater then 35 we insert 42 to the right of node 35. Step 5: Now we have to insert 15. First we compare 15 with the root node which is 45. Since the value of 15 is less then 45 so it is inserted to the left of the root node. But the root node has already one left node 35. So now we compare 15 with 35. Since the value of 15 is less then 35 we insert 15 to the left of node 35. Step 6: Now we have to insert 64. First we compare 64 with the root node which is 45. Since the value of 64 is greater then 45 so it is inserted to the right of the root node. But the root node has already one right node 68. So now we compare 64 with 68. Since the value of 64 is less then 68 we insert 64 to the left of node 68. Step 7: Now we have to insert 78. First we compare 78 with the root node which is 45. Since the value of 78 is greater then 45 so it is inserted to the right of the root node. But the root node has already one right node 68. So now we compare 78 with 68. Since the value of 78 is greater then 68 we insert 78 to the right of node 68.

> 