CODEWITHSUNDEEP
data-structuresbinary-treebig-otime-complexity
Alex L
Alex L

Reputation: 8925

Time complexity of next/previous functions on a BST

I'm interested in the worst-case efficiency of stepping forwards and backwards through binary search trees.

Unbalanced tree:

   5
  /
 1 
  \
   2
    \
     3
      \
       4

It looks like the worst case would be 4->5, which takes 4 operations.

Balanced tree:

   2
  / \
 1   4
    / \ 
   3   5

Worst case is 2->3, which takes 2 operations.

Am I right in thinking that the worst case for any BST is O(height-1), which is O(log n) for balanced trees, and O(n-1) for unbalanced trees?

Upvotes: 2

Views: 355

Answers (2)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

Am I right in thinking that the worst case for any BST is O(height-1), which is O(log n) for balanced trees, and O(n-1) for unbalanced trees?

Yes, you will only ever need to go up or down when travelling from k to k+1, never both (because the invariant is left child < parent < right child).

Although O(height-1) can be written O(height) (and similarly for O(n)).

Upvotes: 3

Captain Giraffe
Captain Giraffe

Reputation: 14705

If you are considering just traversing the tree in order, the complexity does not change with regards to balance. The algorithm is still

 walk( Node n)
    walk( n.left )
    visit( n )
    walk( n.right )

1 op per step.

It's when you start to apply lookups, inserts and deletes the balance comes into play.

And for these operations to be in O(log N ) a balanced tree is required.

If you are trying to find the next element in the sequence defined by the tree, you may be required to travel the entire height of the tree, and of course in a balanced tree this is O ( log N ), and in an unbalanced tree this is O( N)

Upvotes: 1

Related Questions