algoadvance

Leetcode 108. Convert Sorted Array to Binary Search Tree

Problem Statement

Leetcode Problem 108: “Convert Sorted Array to Binary Search Tree”

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree (BST).

A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Example:

Input: nums = [-10, -3, 0, 5, 9]
Output: [0, -3, 9, -10, null, 5]

Clarifying Questions

1. Q: Can the input array be empty?
   • A: Yes, in which case the output should be null.
2. Q: Should the BST values be returned in any specific format?
   • A: As required by the problem, we will return the root node of the BST.

Strategy

1. Approach:
   • Since the input array is sorted in ascending order, we can use a divide-and-conquer strategy.
   • At each step, select the middle element of the current array segment to be the root of the subtree.
   • Recursively apply this to the left and right subarrays to construct the left and right subtrees respectively.
2. Steps:
   • Define a helper function sortedArrayToBST that takes in the array segment’s start and end indices.
   • To get the middle element, calculate middle = (start + end) / 2.
   • Create a tree node with the value at this middle index.
   • Recursively construct the left subtree with the segment from start to middle - 1.
   • Recursively construct the right subtree with the segment from middle + 1 to end.
   • Return the root node.
3. Base Case:
   • If start > end, return null because it means the segment is invalid or all elements have been processed.

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 constructBST(nums, 0, nums.length - 1);
    }

    private TreeNode constructBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = constructBST(nums, start, mid - 1);
        node.right = constructBST(nums, mid + 1, end);

        return node;
    }
}

Time Complexity

• Time Complexity: O(n)
  • Each element in the array is processed once to create tree nodes.
  • Because the array is divided and processed in a balanced manner, each level of recursion operates on portions of the array that get smaller by approximately half.
• Space Complexity: O(log n) for the recursion stack
  • The depth of the recursion is limited to the height of the tree, which is log(n) for a balanced BST with n nodes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?