CODEWITHSUNDEEP
algorithmbinary-search-tree
user2827214
user2827214

Reputation: 1191

Find kth smallest element in O(log n)

I know that if balanced, a BST height is O(log(n)), meaning searching is O(log(n)), but making an unbalanced tree into a balanced one would increase the run-time of inserting / deleting, since you would have to rebalance it after each insertion / deletion.

Is there another way to modify the BST so that I can find the Kth smallest item in O(log(n)) time, without affecting the runtime of other functions?

Upvotes: 2

Views: 2143

Answers (1)

Dennis Meng
Dennis Meng

Reputation: 5187

but making an unbalanced tree into a balanced one would increase the run-time of inserting / deleting, since you would have to rebalance it after each insertion / deletion.

Not true, self-balancing binary trees also have O(log n) insert and delete. The basic reason is that while you do need to do rebalancing, the rebalancing itself will take a total of O(log n) per operation.

Have a look at AVL trees to get an idea of how it's able to rebalance without affecting the complexity of the operations.

Upvotes: 2

Related Questions