Leetcode 1382 - Balance a Binary Search Tree [26/6/24]

Time Taken: ~45 mins
Tag: LeetCode Medium
High-level ideas:
Create a vector sorted in ascending order, containing the values of nodes in tree.
Using the sorted vector, create a balanced BST from scratch recursively.
Use the fact that the left side of BST contains elements smaller than current node, while right side of BST contains elements larger than current node.
Since vector is sorted, we can utilise it to evenly split elements. Each time, get the middle index of the range of vector considered to be the current node, and recursively create left and right balanced BST using the remaining elements to the left and right respectively.