Leetcode 108. Convert Sorted Array to Binary Search Tree

Problem Explanation:

You are given a sorted array of integers and your task is to construct a height-balanced binary search tree (BST) from this array. The BST should be such that the depth of its two subtrees should differ at most by 1.

For example, given the sorted array: [-10,-3,0,5,9], one possible height-balanced BST could be represented as [0,-3,9,-10,null,5], which can be visualized as:

1
2
3  0
4 / \
5-3   9
6/   /
7-10  5

Approach to the Solution:

The approach to implement the solution revolves around the Binary Search Tree (BST) and Recursion concepts. Since the array we receive is sorted, the middle element of the array would be made the root of the BST because in a BST, the left child node should have a value less than its root node and right child node should have a value greater than its root node.

So, if the middle element is chosen as the root, all the elements on the left will be less than the root and all elements on the right will be greater than the root.

Now, the problem of finding a root for left and right subtrees can be solved similarly, which leads us to a divide and conquer strategy.

Algorithm Steps:

• Start with the middle element of the array as the root of the BST.
• Use the elements to the left of this middle element to construct the left subtree, recursively.
• Use the elements to the right of this middle element to construct the right subtree, recursively.
• You now have a root and its left and right subtrees, and therefore, a BST.

Here is example using given array: [-10,-3,0,5,9]

1
2
3// Start from middle node 
4  0
5 / \
6?   ?
7For the left node of 0, middle of array [-10,-3] is -3 and for right node of 0 middle of [5,9] is 9. So:
8
9  0
10 / \
11-3   9
12 /   /
13?   ?
14Choose for each sub-array in a similar manner:
15
16  0
17 / \
18-3   9
19 /   /
20-10  5

Python Solution:

1
2python
3class Solution: 
4    def sortedArrayToBST(self, nums): 
5        if not nums: 
6            return None 
7        mid_val = len(nums) // 2
8        node = TreeNode(nums[mid_val]) 
9        node.left = self.sortedArrayToBST(nums[:mid_val]) 
10        node.right = self.sortedArrayToBST(nums[mid_val + 1:]) 
11        return node

Java Solution:

1
2java
3public class Solution {
4    public TreeNode sortedArrayToBST(int[] nums) {
5        if (nums.length == 0) {
6            return null;
7        }
8        TreeNode root = createBalancedBST(nums, 0, nums.length - 1);
9        return root;
10    }
11
12    private TreeNode createBalancedBST(int[] nums, int start, int end) {
13        if (start > end) {
14            return null;
15        }
16
17        int mid = (start + end) / 2;
18        TreeNode node = new TreeNode(nums[mid]);
19        node.left = createBalancedBST(nums, start, mid - 1);
20        node.right = createBalancedBST(nums, mid + 1, end);
21        return node;
22    }
23}

C++ Solution:

1
2c++
3class Solution {
4public:
5    TreeNode* constructBST(vector<int>& nums, int left, int right) {
6        if (left > right)
7            return NULL;
8        int mid = left + (right - left) / 2;
9        TreeNode* newNode = new TreeNode(nums[mid]);
10        newNode->left = constructBST(nums, left, mid - 1);
11        newNode->right = constructBST(nums, mid + 1, right);
12        return newNode;
13    }
14
15    TreeNode* sortedArrayToBST(vector<int>& nums) {
16        if (nums.size() == 0) 
17            return NULL;
18        return constructBST(nums, 0, nums.size() - 1);
19    }
20};

JavaScript Solution:

1
2javascript
3var sortedArrayToBST = function(nums) {
4    if (nums.length === 0) { 
5        return null; 
6    }
7    var mid = Math.floor(nums.length/2);
8    var root = new TreeNode(nums[mid]);
9    root.left = sortedArrayToBST(nums.slice(0,mid));
10    root.right = sortedArrayToBST(nums.slice(mid + 1));
11    return root;
12};

C# Solution:

1
2csharp
3public class Solution {
4    public TreeNode SortedArrayToBST(int[] nums) {
5        return CreateBalancedBST(nums,0,nums.Length-1);
6    }
7    
8    public TreeNode CreateBalancedBST(int[] nums, int start, int end) {
9        if(start>end)
10            return null;
11        int mid=(start+end)/2;
12        TreeNode node=new TreeNode(nums[mid]);
13        
14        node.left=CreateBalancedBST(nums,start,mid-1);
15        node.right=CreateBalancedBST(nums,mid+1,end);
16        
17        return node;
18    }
19}

In above code, TreeNode is a class which contains value and two child nodes as left and right.This problem is a common interview question because it not only tests understanding of binary trees, but also recursion and application of the divide-and-conquer concept.

Given a sorted array, to create a height-balanced BST, we have to make sure that all left and right subtrees of every node differ by not more than one with respect to their heights. Since the array is sorted, an efficient solution to the problem lies in choosing the middle element as root and then recursively finding roots for left and right subtrees.

Time Complexity:

All the solutions shared have a time complexity of O(n), where n is the number of elements in the array. This is because we iterate through every element of the array once while constructing the BST.

Space Complexity:

The space complexity of the given solutions is also O(n) to accommodate the height of the recursive call stack, in the worst-case scenario.

Conclusion:

Constructing a height-balanced BST from a sorted array is a fundamental problem often encountered during interviews or coding tests. No matter what programming language you use, a strong grasp of binary trees, recursion, and the divide and conquer strategy is crucial to solve this type of problem. The solutions provided in Python, Java, JavaScript, C++, and C# clearly illustrate the concept and should help you understand and solve similar problems.