## DEV Community

MD ARIFUL HAQUE

Posted on • Updated on

# 1382. Balance a Binary Search Tree

1382. Balance a Binary Search Tree

Medium

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`

Solution:

``````/**
* Definition for a binary tree node.
* class TreeNode {
*     public \$val = null;
*     public \$left = null;
*     public \$right = null;
*     function __construct(\$val = 0, \$left = null, \$right = null) {
*         \$this->val = \$val;
*         \$this->left = \$left;
*         \$this->right = \$right;
*     }
* }
*/
class Solution {

/**
* @param TreeNode \$root
* @return TreeNode
*/
function balanceBST(\$root) {
\$nums = [];
\$this->inorder(\$root, \$nums);
return \$this->build(\$nums, 0, count(\$nums) - 1);
}

function inorder(\$root, &\$nums) {
if (\$root == null)
return;
\$this->inorder(\$root->left, \$nums);
\$nums[] = \$root->val;
\$this->inorder(\$root->right, \$nums);
}

function build(\$nums, \$l, \$r) {
if (\$l > \$r)
return null;
\$m = (int)((\$l + \$r) / 2);
return new TreeNode(\$nums[\$m], \$this->build(\$nums, \$l, \$m - 1), \$this->build(\$nums, \$m + 1, \$r));
}
}
``````