108. Convert Sorted Array to Binary Search Tree
Description
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.
Constraints
Approach
Links
YouTube
Examples
Input: [-10, -3, 0, 5, 9]
Output: [0, -10, 5, null, -3, null, 9]
One possible answer is: [0, -10, 5, null, -3, null, 9], which represents the following height balanced BST:
Solutions
// 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;
}
}/**
* Time complexity : O(N) since we visit each node exactly once.
* Space complexity : O(N) to keep the output, and O(logN) for the
* recursion stack.
*/
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 start, int end) {
if(start > end) return null;
int index = (start + end)/2;
TreeNode node = new TreeNode(nums[index]);
node.left = sortedArrayToBST(nums, start, index-1);
node.right = sortedArrayToBST(nums, index+1, end);
return node;
}
}Follow up
Sorted Linked List to Balanced BST - GFG
Last updated
Was this helpful?