Convert Sorted Array to Binary Search Tree

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

  1. 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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s