Binary Search Trees: Given a sorted array, convert into balanced bst

Problem Statement:

Given a sorted array, convert into balanced bst

Example:

Input: arr = [1, 2, 3]

Output:

    /*
     *           2
     *         /    \
     *        1      3
     */

Solution Explanation:

We will use recursion to solve the problem

Find the middle element in the array, and recursively process the left and right subarray

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Tree_Node 
{
public:
	int data;
	Tree_Node* left;
	Tree_Node* right;

	Tree_Node(int x) 
	{
		data = x;
		left = nullptr;
		right = nullptr;
	}
};

void inorderTraversal(Tree_Node* root)
{
    if (!root)
        return;
    inorderTraversal(root->left);
    cout<<root->data<< " " ;
    inorderTraversal(root->right);
}

Tree_Node* solution(vector<int>& arr, int start, int end) 
{
    if (start > end) 
    	return nullptr;

    int mid = start + (end - start) / 2;
    
    Tree_Node* root = new Tree_Node(arr[mid]);

    root->left = solution(arr, start, mid - 1);
    root->right = solution(arr, mid + 1, end);

    return root;
}


int main()
{


    /*
     *           2
     *         /    \
     *        1      3
     */

    vector<int> arr = {1, 2, 3};

    Tree_Node* root = solution(arr, 0, arr.size()-1);
    
    inorderTraversal(root);

    return 0;
}

Output

1 2 3