Hi Geeks! Welcome to 100 Days of Leetcode Challenge. In this article, we going to see about how to Convert Sorted Array to Binary Search Tree.

**Day 45 of 100**

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

**Example:**

Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5

## Solution

Before seeing the solution, **think 3 to 5 minutes, how will you approach this problem? How can you come with the solution? **If you really got some approach or solution, to solve this problem, please share it in comment section.

### Approach

- Insert nodes in Tree with Binary Search because the given array is sorted.

**Recursion – DFS Approach**

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode SortedArrayToBST(int[] nums) { if(nums.Length == 0) return null; TreeNode root = helper(nums,0,nums.Length-1); return root; } public TreeNode helper(int[] nums,int low,int high) { //We done if(low > high){ return null; } //Best way to handle Integer overflows int mid = low + (high - low)/2; TreeNode root = new TreeNode(nums[mid]); root.left = helper(nums,low,mid-1); root.right = helper(nums,mid+1,high); return root; } }

Time Complexity: O(n)

Space Complexity: O(n)