algoadvance

Leetcode 108. 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 (BST).

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.

Clarifying Questions

  1. Are there any constraints on the size of the input array?
    • Typically, the array size is within the range of typical interview problems and should efficiently fit in memory.
  2. Is the array guaranteed to have unique elements?
    • Yes, for simplicity, it’s assumed that all elements in the sorted array are unique.
  3. What should be the return structure of the function?
    • The function should return the root of the resulting height-balanced BST.

Strategy

  1. Recursive Approach:
    • To create a height-balanced BST, the middle element of the array/subarray should be used as the root.
    • The left half of the array will form the left subtree, and the right half will form the right subtree.
    • Recursively repeat this process for each subtree.
  2. Steps:
    • Find the middle element of the array.
    • Create a new tree node with the middle element as the root.
    • Recursively do the same for the left subarray to get the left child and the right subarray to get the right child.

Time Complexity

Code

Here’s the C++ implementation for converting a sorted array to a height-balanced BST:

#include <vector>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* sortedArrayToBST(std::vector<int>& nums) {
        return sortedArrayToBSTHelper(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* sortedArrayToBSTHelper(const std::vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        
        // Find the middle element of the current subarray
        int mid = left + (right - left) / 2;
        
        // Create a tree node with the middle element
        TreeNode* node = new TreeNode(nums[mid]);
        
        // Recursively build the left and right subtrees
        node->left = sortedArrayToBSTHelper(nums, left, mid - 1);
        node->right = sortedArrayToBSTHelper(nums, mid + 1, right);
        
        return node;
    }
};

This implementation ensures that the BST is height-balanced by picking the middle element of the current array/subarray to be the root of the tree. The left and right components are handled recursively to form subtrees.

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