Balance a Binary Search Tree

Given the root of a binary search tree, return a height-balanced BST containing the same node values. Pattern focus: Convert Sorted Array to BST. Perform an inorder traversal to obtain sorted values, then rebuild the tree from the middle elements.

Input Format

root = binary tree root

Output Format

root of a height-balanced BST containing the same values

Constraints

  • 0 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [1,null,2,null,3,null,4,null,5]

Output:

[3,2,5,1,null,4]

Explanation:

The skewed tree is rebuilt into a balanced BST.

Example 2:

Input:

root = [4,3,null,2,null,1]

Output:

[3,2,4,1]

Explanation:

The sorted values are reassembled around the middle value 3.

Loading...
Balance a Binary Search Tree