First thing to remember is that when we do inorder traversal on a Binary Search Tree (BST) we can get back a sorted array. Then based on this sorted array of tree nodes we can re-construct a balanced BST and return the node. However, this is a bit tricky because we cannot just start from the beginning and keep adding nodes because in that way the tree will not be balanced. What I learned from one of the LeetCode discussion is an elegant recursion solution:
The nice thing about this algo is that it takes the middle point and treat it as the root, then assign left and right node recursively. Therefore, every node that became the new root will actually always be the middle value one so the tree will not be unbalanced.
For example if we have an array like 2 4 5 7 8 9
In the first execution the left will be 2 and right will be 9 and middle will be 5. Then when we assign root.left we go into the next recursive call and left became 2 and right became 4 and middle became 2. Therefore, the new root which will be the left child of 5 is 2 and the right child of 2 will be 4. As we repeat the process we will get 8 to be the right child of 5 and 7&9 will be 8’s children.
