The algorithm to insert an element k into binary search tree is as follows:-
/* Get a new node and make it a leaf*/
getnode (k)
left(k) = null
right(k) = null
info (k) = x
/* Initialize the traversal pointers */
p = root
trail = null
/* search for the insertion place */
while p <> null do
begin
trail = p
if info (p) > x
then p = left (p)
else
p = right (p)
end
/* To adjust the pointers */
If trail = null
Then root = k /* attach it as a root in the empty tree */
else
if info (trail) > x
then
left (trail) = k
else
right (trail) = k
Analysis : - We notice that the shape of binary tree is determined by the order of insertion. If the values are sorted in ascending or descending order, the resulting tree will have maximum depth equal to number of input elements. The shape of the tree is important from the point of view of search efficiency. The depth of the tree determines the maximum number of comparisons. Therefore we can maximize search efficiency by minimizing the height of the tree.
eg. For the values as 6, 7, 8, 9, 10
the binary tree formed would be as follows
