Sarthaks Test
+1 vote
in Computer by (68.8k points)

Write an algorithm to insert an element k into binary search tree. Give the analysis and example. 

1 Answer

+2 votes
by (69.3k points)
selected by
Best answer

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 


trail = p

if info (p) > x

then p = left (p)


p = right (p)


/* To adjust the pointers */

If trail = null

Then root = k /* attach it as a root in the empty tree */


if info (trail) > x


left (trail) = k 


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

Related questions

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.