# 13. Balance a Binary Search Tree

Given a binary search tree, return a **balanced** binary search tree with the same node values.

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

If there is more than one answer, return any of them.

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/08/22/1515_ex1.png)![](https://assets.leetcode.com/uploads/2019/08/22/1515_ex1_out.png)

```
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,null,null] is also correct.
```

## Solution: (Using Inorder and Recursion)

**Approach:**\
**Get the sorted array using inorder traversal**\
**Use recursion to create a tree:**\
       **Find mid**\
       **Left array is the left subtree and right array is right subtree**

```cpp
class Solution
{
public:
    TreeNode *createTree(vector<int> v, int start, int end)
    {

        if (start > end)
        {
            return NULL;
        }

        int mid = (start + end) / 2;
        TreeNode *temp = new TreeNode;
        temp->val = v[mid];

        temp->left = createTree(v, start, mid - 1);
        temp->right = createTree(v, mid + 1, end);
        return temp;
    }
    
    TreeNode *balanceBST(TreeNode *root)
    {

        stack<TreeNode *> s;
        vector<int> v;
        TreeNode *t = root;

        while (!s.empty() || t != NULL)
        {

            if (t != NULL)
            {
                s.push(t);
                t = t->left;
            }
            else
            {
                t = s.top();
                s.pop();
                v.push_back(t->val);
                t = t->right;
            }
        }

        TreeNode *res = createTree(v, 0, v.size() - 1);
        return res;
    }
};
```

**Time Complexity: O(n)**

#### Using the same node instead of creating new node. New node creation takes more time

```cpp
class Solution
{
public:
    TreeNode *createTree(vector<TreeNode *> &v, int start, int end)
    {

        if (start > end)
        {
            return NULL;
        }

        int mid = (start + end) / 2;
        TreeNode *temp = v[mid];

        temp->left = createTree(v, start, mid - 1);
        temp->right = createTree(v, mid + 1, end);
        return temp;
    }

    TreeNode *balanceBST(TreeNode *root)
    {

        stack<TreeNode *> s;
        vector<TreeNode *> v;
        
        TreeNode *t = root;

        while (!s.empty() || t != NULL)
        {

            if (t != NULL)
            {
                s.push(t);
                t = t->left;
            }
            else
            {
                t = s.top();
                s.pop();
                v.push_back(t);
                t = t->right;
            }
        }

        TreeNode *res = createTree(v, 0, v.size() - 1);
        return res;
    }
};
```