Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Example:

Input:  arr={-10,-3,0,5,9}
Output: tree=[0,-10,5,null,-3,null,9]

Approach

Java

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

public class ConvertSortedArrayBST {
    public static void main(String[] args) {
        int[] arr = { -10, -3, 0, 5, 9 };
        TreeNode root = sortedArrayToBST(arr);
        System.out.print("[");
        printTree(root);
        System.out.println("]");
    }

    static TreeNode sortedArrayToBST(int[] nums) {

        TreeNode root = sortedArrayToBST(nums, 0, nums.length - 1);
        return root;
    }

    static TreeNode sortedArrayToBST(int[] v, int start, int end) {
        if (start > end)
            return null;
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(v[mid]);
        root.left = sortedArrayToBST(v, start, mid - 1);
        root.right = sortedArrayToBST(v, mid + 1, end);
        return root;
    }

    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;
        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;
    }
};


TreeNode *sortedArrayToBST(vector<int> &v,int start,int end)
{
        if(start>end)
              return NULL;
        int mid=start+(end-start)/2;
        TreeNode *root=new TreeNode(v[mid]);
        root->left=sortedArrayToBST(v,start,mid-1);
        root->right=sortedArrayToBST(v,mid+1,end);
        return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums)
{
        
        TreeNode *root=sortedArrayToBST(nums,0,nums.size()-1);
        return root;
}
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()
{
  vector<int> arr={-10,-3,0,5,9};
  TreeNode *root=sortedArrayToBST(arr);
  cout<<"[";
  printTree(root);
  cout<<"]";
  return 0;
}