[Google] Transform a unbalanced tree into balanced tree

Question

link

How to transform a unbalanced tree into balanced tree?

Solution

Solution 1, do AVL tree balancing. Refer to [Design] BST Node Insertion / Deletion. This is of course, pretty difficult to code.

Best solution is to convert to DLL and then build a new tree!

Code

not written