Search code examples
comparisonbinary-treebinary-search-tree

Number of comparisons when building a binary search tree

I am learning binary search trees by myself. There is a question that asks how many comparisons it takes to build a tree when inserting the letters E, A, S, Y, Q, U, E, S, T, I, O and N in an initially empty tree.

I drew the binary search tree and I counted the number of comparisons when inserting each element. 

 E 
/ \
A  S
   /\
  Q  Y
 /   /
 E   U
 \   /
  I  S
   \  \
    O  T
    /
    N

I got 36.

Is that correct? Also, is there another way to know the number of comparisons without having to draw the tree?

Solution

  • Number of comparisons will be 36 .

    You can conclude that maximum number of comparisons to insert an element in BST will not be more than height of the tree.