CODEWITHSUNDEEP
algorithmtime-complexitybinary-search-tree
Mr.Php
Mr.Php

Reputation: 109

Time analysis on BST

I know, time analysis of BST is O(h), where h is height of the tree.

Is it possible for a search on a BST take O(n) to complete?

Upvotes: 0

Views: 83

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55589

Yes it is. This tree for example:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7
             \
              8

It takes n (8) comparisons when looking for the value 8 or greater.

Upvotes: 3

Related Questions