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