Coding Mines: Convert Sorted Array to Binary Search Tree LeetCode (Sorted Array to Balanced BST)

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.

NOTE:

This problem is popular in LeetCode and GeeksForGeeks A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions

Solution:

Source: Java

	/*
	* To change this license header, choose License Headers in Project Properties.
	* To change this template file, choose Tools \| Templates
	* and open the template in the editor.
	*/
	package com.alg.leetup;

	/**
	*
	* Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
	*
	*
	* Solution 1:
	* Recursive approach:
	* 1)Get the middle of the array and make it as a root
	* 2) left half (excluding root) will be the left subtree of root
	* 3) right half(excluding root) will be the right subtree of root
	* 4)recursively make BST from left half
	* 5)recursively make BST from right half
	*
	*
	* @author rbaral
	*/
	public class SortedArrayToBST {
	public TreeNode sortedArrayToBST(int[] nums) {
	if(nums==null \|\| nums.length==0){
	return null;
	}
	TreeNode root = null;
	root = getBST(nums, 0, nums.length-1);
	return root;
	}

	public TreeNode getBST(int[] nums, int start, int end){
	if(nums.length==0 \|\|(start>end)){
	return null;
	}
	else if(nums.length==1){
	return new TreeNode(nums[0]);
	}else{
	//get the middle
	int mid = (start+end)/2;

	TreeNode root = new TreeNode(nums[mid]);
	root.left = getBST(nums, start, mid-1);
	root.right = getBST(nums,mid+1, end);
	return root;
	}
	}
	}

Coding Mines