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 differs by more than 1.

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

Example :

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.

Approach:

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BalanceBinarySearchTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        root.right.right.right = new TreeNode(4);

        TreeNode res = balanceBST(root);
        printTree(res);
    }

    static TreeNode balanceBST(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        dfs(root, res);

        return construct(res, 0, res.size() - 1);
    }

    static void dfs(TreeNode node, List<Integer> res) {
        if (node == null)
            return;
        dfs(node.left, res);
        res.add(node.val);
        dfs(node.right, res);
    }

    static TreeNode construct(List<Integer> res, int start, int end) {
        if (start < 0 || end >= res.size() || start > end)
            return null;

        int mid = start + (end - start) / 2;

        TreeNode root2 = new TreeNode(res.get(mid));
        root2.left = construct(res, start, mid - 1);
        root2.right = construct(res, mid + 1, end);
        return root2;
    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            root = q.poll();
            if (root == null)
                vec.add("null");
            else
                vec.add(String.valueOf(root.val));
            if (root != null) {
                q.add(root.left);
                q.add(root.right);
            }
        }
        int j = vec.size() - 1;
        while (j > 0 && vec.get(j) == "null")
            j--;
        for (int i = 0; i < j; i++)
            System.out.print(vec.get(i) + ",");
        System.out.print(vec.get(j));
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
void dfs(TreeNode *node, vector<int> &res)
{
    if (!node)
        return;
    dfs(node->left, res);
    res.push_back(node->data);
    dfs(node->right, res);
}
TreeNode *construct(vector<int> &res, int start, int end)
{
    if (start < 0 || end >= res.size() || start > end)
        return NULL;

    int mid = start + (end - start) / 2;

    TreeNode *root2 = new TreeNode(res[mid]);
    root2->left = construct(res, start, mid - 1);
    root2->right = construct(res, mid + 1, end);
    return root2;
}
TreeNode *balanceBST(TreeNode *root)
{
    vector<int> res;
    dfs(root, res);

    return construct(res, 0, res.size() - 1);
}

void printTree(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    vector<string> vec;
    while (!q.empty())
    {
        root = q.front();
        q.pop();
        if (root == NULL)
            vec.push_back("null");
        else
            vec.push_back(to_string(root->data));
        if (root != NULL)
        {
            q.push(root->left);
            q.push(root->right);
        }
    }
    int j = vec.size() - 1;
    while (j > 0 && vec[j] == "null")
        j--;
    vec.resize(j);
    for (int i = 0; i < j; i++)
        cout << vec[i] << ",";
    cout << vec[j];
}

int main()
{
    TreeNode *root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->right = new TreeNode(3);
    root->right->right->right = new TreeNode(4);

    TreeNode *res = balanceBST(root);

    cout << "[";
    printTree(res);
    cout << "]";
    return 0;
}