Problem

Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them.

A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.

Examples

Example 1:

1
 \
  2
   \
    3
     \
      4

Outputs

  2
 / \
1   3
     \
      4

OR

  3
 / \
1   4
 \   
  2  

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

Example 2:

Input: root = [2,1,3]
Output: [2,1,3]

Solution

Method 1 - Inorder traversal to sorted array to balanced BST

We can use the solution from Convert Sorted Array to height-balanced Binary Search Tree. The idea is:

Here is the video explanation:

Code

Java

Because in java, we should know the length of the array to create, we will use List instead.

class Solution {
	List<TreeNode> sortedList = new ArrayList<>();

	public TreeNode balanceBST(TreeNode root) {
		inorderTraverse(root);
		return sortedListToBST(0, sortedList.size() - 1);
	}

	void inorderTraverse(TreeNode root) {
		if (root == null){
			return;
		} 
		inorderTraverse(root.left);
		sortedList.add(root);
		inorderTraverse(root.right);
	}

	TreeNode sortedListToBST(int start, int end) {
		if (start > end) {
			return null;
		}
		
		int mid = (start + end) / 2;
		TreeNode root = sortedList.get(mid);
		
		root.left = sortedListToBST(start, mid - 1);
		root.right = sortedListToBST(mid + 1, end);
		
		return root;
	}
}

Complexity

  • ⏰ Time complexity: O(n) where n is number of nodes in BST. It takes O(n) time to do inorder traversal, and then O(n) time to convert array to height-balanced BST.
  • 🧺 Space complexity: O(n) assuming recursion stack and also for storing sorted array.