Solution For Convert Sorted Array To Binary Search Tree

Problem Statement:
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.

Solution Approach:
To solve this problem, we need to build a balanced binary search tree from the given sorted array. Since the array is sorted in ascending order, we can always look for the middle element of the array and make it the root of the binary search tree. Then, we can recursively build the left and right sub-trees of the root node using the left and right half of the array respectively.

To implement this approach, we can define a recursive function named sortedArrayToBST that takes in the sorted array and the starting and ending index of the array as parameters. In each recursive call, we can look for the middle element of the sub-array and make it the root of the subtree. Then, we can recursively call the sortedArrayToBST function for the left and right halves of the sub-array and attach them to the left and right pointers of the root node respectively.

Algorithm:

1. Define a recursive function named sortedArrayToBST that takes in the sorted array nums, the starting index lo, and the ending index hi as parameters.
2. If the starting index lo is greater than the ending index hi, return null.
3. Compute the middle index mid as (lo + hi) / 2.
4. Create a new TreeNode node with the value nums[mid].
5. Recursively call the sortedArrayToBST function for the left sub-array with lo index as lo and hi index as mid – 1 and attach the returned subtree to the left pointer of the node.
6. Recursively call the sortedArrayToBST function for the right sub-array with lo index as mid + 1 and hi index as hi and attach the returned subtree to the right pointer of the node.
7. Return the node.

Let’s implement it in code:

“`
/*
* Definition for a binary tree node.
* public 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;
* }
* }
/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return sortedArrayToBST(nums, 0, nums.length – 1);
}

private TreeNode sortedArrayToBST(int[] nums, int lo, int hi) {
    if (lo > hi) {
        return null;
    }
    int mid = (lo + hi) / 2;
    TreeNode node = new TreeNode(nums[mid]);
    node.left = sortedArrayToBST(nums, lo, mid - 1);
    node.right = sortedArrayToBST(nums, mid + 1, hi);
    return node;
}

}
“`

The time complexity of this approach is O(n) because we are processing each element of the array only once. The space complexity is also O(n) because we are creating an additional TreeNode for each element of the array.

Step by Step Implementation For Convert Sorted Array To Binary Search Tree

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        
        TreeNode root = new TreeNode(nums[nums.length / 2]);
        root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, nums.length / 2));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, nums.length / 2 + 1, nums.length));
        return root;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        # base case
        if not nums:
            return None
        
        # find the middle element of the array
        mid = len(nums) // 2
        
        # create the root node
        root = TreeNode(nums[mid])
        
        # create the left and right subtrees recursively
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        
        return root

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if(!nums.length) return null;
    
    const middle = Math.floor(nums.length / 2);
    const root = new TreeNode(nums[middle]);
    
    root.left = sortedArrayToBST(nums.slice(0, middle));
    root.right = sortedArrayToBST(nums.slice(middle + 1));
    
    return root;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector& nums) {
        if(nums.size() == 0) return NULL;
        int mid = nums.size() / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        vector left(nums.begin(), nums.begin() + mid);
        vector right(nums.begin() + mid + 1, nums.end());
        root->left = sortedArrayToBST(left);
        root->right = sortedArrayToBST(right);
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        // Base case
        if (nums.Length == 0) {
            return null;
        }
        
        // Recursive case
        int mid = nums.Length / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = SortedArrayToBST(nums.Take(mid).ToArray());
        root.right = SortedArrayToBST(nums.Skip(mid + 1).ToArray());
        return root;
    }
}