I searched that question but didn't understand the answer that is: We can traverse the tree in O(n) time and insert each element into an initially empty AVL tree; this will take O(nlogn) time overall. To get O(n) ‘best-case’ performance we can do something that’s a bit of a hack: try to verify that the BST is a valid AVL tree, which we can do in O(n) time; if it is, return it as it is. Otherwise, create a new AVL tree as described. It’s questionable as to whether this is really a ‘bestcase’ result, as we don’t actually do any conversion, only verification.

1 Year
Discussion Span
Last Post by deceptikon

Technically the best case is the input tree is already AVL balanced, so the solution is legit from a complexity standpoint. The more practical problem with this solution is it adds a verification step regardless of the input tree and slows down the algorithm even when you need to adjust balance.

To properly determine if the solution is worth the cost, you'd need to measure how much of an impact the verification step has and compare against the probability of receiving a valid AVL tree as input. That leaves the realm of complexity theory, but it's something that must be done with actual code.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.