In a recent interview i was asked to convert a BST into height balanced BST. I provided the solution that "we will first get the inorder traversal of the BST to get the values in a list and then will choose the middle element and will recursively build right and left child". I was told that it will work but it will consume O(N) extra space and asked to do it inplace on the origional tree. I
thought for finding the solution but could not. Is it even possible, if yes how?
