Frontend School

Convert Sorted Array to Balanced BST

DSA
easy

Convert Sorted Array to Balanced BST

Easy
Tree
Binary Search Tree
Recursion
Divide and Conquer

Overview

In many applications, data needs to be stored and retrieved efficiently. Binary Search Trees (BSTs) are excellent data structures for this purpose, offering logarithmic time complexity for search, insertion, and deletion operations on average. However, if a BST becomes unbalanced, these operations can degrade to linear time. This problem challenges you to construct a balanced BST from a sorted array, ensuring optimal performance characteristics for subsequent operations.

What you need to do / Task

You are given an integer array nums where the elements are sorted in ascending order and are unique. Your task is to convert this array into 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.

Implement the function sortedArrayToBST which takes the sorted array nums and returns the root of the constructed height-balanced BST.

Input & output

  • Input: nums — An array of integers, sorted in ascending order. All integers are unique.
  • Output: The root of the constructed height-balanced Binary Search Tree. If the input array is empty, return null.

Clarifications

  • Empty input: If nums is an empty array, the function should return null.
  • Balanced definition: A height-balanced binary tree is one where for every node, the height difference between its left and right subtrees is at most 1.
  • Multiple valid BSTs: There might be multiple valid height-balanced BSTs for a given sorted array. Any valid construction will be accepted.

Examples

1

Example 1

Input:

nums = [-10,-3,0,5,9]

Output:

[0,-3,9,-10,null,5]

Note:

One possible height-balanced BST. The root is 0, left child is -3, right child is 9. -3's left child is -10. 9's left child is 5.

2

Example 2

Input:

nums = [1,2,3,4]

Output:

[3,2,4,1]

Note:

Another valid height-balanced BST. The root is 3, left child is 2, right child is 4. 2's left child is 1.

3

Example 3

Input:

nums = [7]

Output:

[7]

Note:

A single-element array results in a single-node BST.

4

Example 4

Input:

nums = []

Output:

null

Note:

An empty array should return null.

Constraints

Constraints & assumptions

  • 0 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in a strictly increasing order.
  • All values in nums are unique.
  • The TreeNode class will be provided in the execution environment. Its definition is standard:
    class TreeNode {
        val: number
        left: TreeNode | null
        right: TreeNode | null
        constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
            this.val = (val===undefined ? 0 : val)
            this.left = (left===undefined ? null : left)
            this.right = (right===undefined ? null : right)
        }
    }
    

Out of scope

  • Input validation (assume nums is always a sorted array of unique integers within the specified range).
  • Optimizing for space complexity beyond what is inherent to tree construction (O(N) for nodes, O(log N) for recursion stack).

What interviewers evaluate

  • Correctness: Does the generated tree satisfy BST properties and is it height-balanced?
  • Efficiency: Is the solution optimal in terms of time and space complexity?
  • Edge Cases: How well does the code handle empty arrays or single-element arrays?
  • Code Quality: Is the code clean, readable, and well-structured?

Loading editor...