- Adding a new node in the binary tree should not violate the properties of the binary tree
- the root value is checked with the root node
- case 1: If the new node value is less than the root value traversing should be done left subtree.
- case 2: If the new node value is greater than the root value traversing should be done right subtree.
- The search pointer moves down until it reaches the leaf node. the insertion function requires time proportional to the height of the tree.in the most case, it takes o(log n) time to execute in the average it lakes o(n)
lets look into one example:
insert 41 in the below binary tree
step 1: compare 41 with the root node 35. (41>35)41 is greater than 35 so traversal should be done on the right subtree
step 2:compare 41 with root node 43. (41<43) 41 is lesser than 43 so traversal should be done on the left sub tree
step 3: compare 41 with root node 39. (41>39) 41 is greater than 39 so traversal should be done on the right subtree, but there is no sub-nodes for the root node, a new node should be inserted as a right subtree