1382. Balance a Binary Search Tree LeetCode Solution

In this guide, you will get 1382. Balance a Binary Search Tree LeetCode Solution with the best time and space complexity. The solution to Balance a Binary Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Balance a Binary Search Tree solution in C++
Balance a Binary Search Tree solution in Java
Balance a Binary Search Tree solution in Python
Additional Resources

1382. Balance a Binary Search Tree LeetCode Solution image

Problem Statement of Balance a Binary Search Tree

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.

Example 1:

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]

Constraints:

The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 105

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1382. Balance a Binary Search Tree LeetCode Solution in C++

class Solution {
 public:
  TreeNode* balanceBST(TreeNode* root) {
    vector<int> nums;
    inorder(root, nums);
    return build(nums, 0, nums.size() - 1);
  }

 private:
  void inorder(TreeNode* root, vector<int>& nums) {
    if (root == nullptr)
      return;
    inorder(root->left, nums);
    nums.push_back(root->val);
    inorder(root->right, nums);
  }

  // Same as 108. Convert Sorted Array to Binary Search Tree
  TreeNode* build(const vector<int>& nums, int l, int r) {
    if (l > r)
      return nullptr;
    const int m = (l + r) / 2;
    return new TreeNode(nums[m], build(nums, l, m - 1), build(nums, m + 1, r));
  }
};
/* code provided by PROGIEZ */

1382. Balance a Binary Search Tree LeetCode Solution in Java

class Solution {
  public TreeNode balanceBST(TreeNode root) {
    List<Integer> nums = new ArrayList<>();
    inorder(root, nums);
    return build(nums, 0, nums.size() - 1);
  }

  private void inorder(TreeNode root, List<Integer> nums) {
    if (root == null)
      return;
    inorder(root.left, nums);
    nums.add(root.val);
    inorder(root.right, nums);
  }

  // Same as 108. Convert Sorted Array to Binary Search Tree
  private TreeNode build(List<Integer> nums, int l, int r) {
    if (l > r)
      return null;
    final int m = (l + r) / 2;
    return new TreeNode(nums.get(m), build(nums, l, m - 1), build(nums, m + 1, r));
  }
}
// code provided by PROGIEZ

1382. Balance a Binary Search Tree LeetCode Solution in Python

class Solution:
  def balanceBST(self, root: TreeNode | None) -> TreeNode | None:
    nums = []

    def inorder(root: TreeNode | None) -> None:
      if not root:
        return
      inorder(root.left)
      nums.append(root.val)
      inorder(root.right)

    inorder(root)

    # Same as 108. Convert Sorted Array to Binary Search Tree
    def build(l: int, r: int) -> TreeNode | None:
      if l > r:
        return None
      m = (l + r) // 2
      return TreeNode(nums[m],
                      build(l, m - 1),
                      build(m + 1, r))

    return build(0, len(nums) - 1)
 # code by PROGIEZ