Convert Sorted Array to Binary Search Tree

Easy
1888.

Convert Sorted Array to Binary Search Tree

EasyArrayDivide and ConquerTreeAmazonMicrosoftGoogleMeta

Convert Sorted Array to Binary Search Tree is an easy coding problem on arrays, trees and divide and conquer, asked in Amazon, Google, Microsoft and Meta interviews.

You are given an integer array nums sorted in strictly increasing order. Build a height-balanced binary search tree holding exactly these values — one in which the depths of the two subtrees of every node differ by at most one — and return its root.

Many balanced trees are possible, so build this one: the root of every range nums[lo..hi] is its left-middle element nums[(lo + hi) / 2] (integer division), the elements before it form the left subtree and the elements after it the right subtree, built the same way.

Example 1

Input
nums = [-10,-3,0,5,9]
Output
[0,-10,5,null,-3,null,9]
Explanation
0 is the middle element. The left half [-10,-3] takes its left-middle -10 as root with -3 to its right; the right half [5,9] likewise takes 5 with 9 to its right.

Example 2

Input
nums = [1,3]
Output
[1,null,3]
Explanation
With two elements the left-middle one, 1, is the root.

Example 3

Input
nums = [7]
Output
[7]
Explanation
A single element is a single node.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in strictly increasing order
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Convert Sorted Array to Binary Search Tree — Solution

Convert Sorted Array to Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Convert Sorted Array to Binary Search Tree is an easy coding problem on arrays, trees and divide and conquer, asked in Amazon, Google, Microsoft and Meta interviews.

Problem statement

You are given an integer array nums sorted in strictly increasing order. Build a height-balanced binary search tree holding exactly these values — one in which the depths of the two subtrees of every node differ by at most one — and return its root.

Many balanced trees are possible, so build this one: the root of every range nums[lo..hi] is its left-middle element nums[(lo + hi) / 2] (integer division), the elements before it form the left subtree and the elements after it the right subtree, built the same way.

Example 1

Input: nums = [-10,-3,0,5,9]
Output: [0,-10,5,null,-3,null,9]
Explanation: 0 is the middle element. The left half [-10,-3] takes its left-middle -10 as root with -3 to its right; the right half [5,9] likewise takes 5 with 9 to its right.

Example 2

Input: nums = [1,3]
Output: [1,null,3]
Explanation: With two elements the left-middle one, 1, is the root.

Example 3

Input: nums = [7]
Output: [7]
Explanation: A single element is a single node.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in strictly increasing order

Hints for Convert Sorted Array to Binary Search Tree

  1. Hint 1

    The root of a balanced search tree over a sorted range should split the range into two halves of nearly equal size.

  2. Hint 2

    Once the root is chosen, the left and right halves are the same problem on smaller ranges.

  3. Hint 3

    Recurse on index ranges [lo, hi] with mid = (lo + hi) / 2; an empty range (lo > hi) gives null.

How to solve Convert Sorted Array to Binary Search Tree

In-order traversal of a search tree is the sorted array, so any node can root a range as long as smaller elements go left and larger go right. Choosing the middle element each time keeps the two sides within one element of each other, which keeps the tree balanced.

Approach

  1. Define build(lo, hi): if lo > hi, return null.
  2. Let mid = (lo + hi) / 2 and create a node with nums[mid].
  3. Set its left child to build(lo, mid - 1) and its right child to build(mid + 1, hi).
  4. Return build(0, n - 1).

Why it works

Every element left of mid is smaller and every element right of it is larger, so the search-tree property holds at each node. The two halves differ in size by at most one, so by induction their heights differ by at most one as well.

Complexity

  • Time — O(n)
  • Space — O(log n) for the recursion (plus the n nodes of the answer)

Pitfalls

  • Use the left-middle element (lo + hi) / 2, as the statement fixes — the right-middle also balances but builds a different tree.
  • Pass indices, not copies of sub-arrays, or the copying costs O(n log n).

Reference solution

Python

from typing import List, Optional

def sortedArrayToBST(nums: List[int]) -> Optional[TreeNode]:
    def build(lo: int, hi: int) -> Optional[TreeNode]:
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        return TreeNode(nums[mid], build(lo, mid - 1), build(mid + 1, hi))
    return build(0, len(nums) - 1)

Java

public static TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

static TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) return null;
    int mid = (lo + hi) / 2;
    return new TreeNode(nums[mid], build(nums, lo, mid - 1), build(nums, mid + 1, hi));
}

C++

TreeNode* build(vector<int>& nums, int lo, int hi);

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return build(nums, 0, (int) nums.size() - 1);
}

TreeNode* build(vector<int>& nums, int lo, int hi) {
    if (lo > hi) return nullptr;
    int mid = (lo + hi) / 2;
    return new TreeNode(nums[mid], build(nums, lo, mid - 1), build(nums, mid + 1, hi));
}

JavaScript

var sortedArrayToBST = function(nums) {
    return build(nums, 0, nums.length - 1);
};

var build = function(nums, lo, hi) {
    if (lo > hi) return null;
    var mid = (lo + hi) >> 1;
    return new TreeNode(nums[mid], build(nums, lo, mid - 1), build(nums, mid + 1, hi));
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Trees and Tree Traversals