in Programming
1,502 views
1 vote
1 vote

Time complexity to compute the sum of k smallest element in the binary search tree??

can we do it like this-

Start doing the inorder traversal of the binary search tree, it will give the elements in increasing order. Start the counter k=0. As we get the elements we increment the counter and then stop the traversal when count reaches k and sum the elements which we have got. Its time complexity will be O(h+k).

Am i right??

plzz plzz explain someone

in Programming
1.5k views

4 Comments

@ Rishabh,

we have to find the sum of k smallest numbers. so we will stop when our count will reach k. If u want to find the sum of n elements that is all the elements then just simply do any traversal and find the sum in O(n) time.
1
1
Complexity will be O(k)

or

we can say complexity O(N) in worst case.

as element could be (N-1) th element in worst case
1
1
@ Sushmita
 sorry i thought that we have to find the k th smallest element
but yeah the concept will remain the same .
0
0

1 Answer

3 votes
3 votes

Time Complexity : O(h) where h is height of tree.

 go to this link http://www.geeksforgeeks.org/sum-k-smallest-elements-bst/