Convert Sorted Array to Binary Search Tree

Easy Trees & BST BST Basics Original on LeetCode

Reported atAppleAirbnbPaytm

Convert Sorted Array to Binary Search Tree is a easy trees & bst problem solved with the bst basics pattern. The best approach, optimal (divide and conquer on index bounds), runs in O(n) time and O(log n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from recursion with copied halves up.

Problem

You are given an integer array nums sorted in strictly increasing order. Build a height-balanced binary search tree that contains exactly these values and return its root.

Height-balanced means that for every node, the heights of its left and right subtrees differ by at most one. Many trees satisfy this; any of them is accepted. Trees are shown in level order, with null for a missing child.

Examples

Example 1

Input
nums = [-6, -2, 0, 4, 9]
Output
[0, -6, 4, null, -2, null, 9]
Why
0 is the middle value. Its left half [-6, -2] and right half [4, 9] become balanced subtrees. Other balanced shapes, like [0, -2, 9, -6, null, 4], are also accepted.

Example 2

Input
nums = [5, 8]
Output
[5, null, 8]
Why
Either value can be the root; [8, 5] is accepted too.

Example 3

Input
nums = [7]
Output
[7]
Why
A single value becomes a single node.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Recursion with copied halvesO(n log n)O(n log n)
Optimal (divide and conquer on index bounds)O(n)O(log n)

1Recursion with copied halves

TimeO(n log n)Each of the log n levels of recursion copies about n values in total.
SpaceO(n log n)Copies along one root-to-leaf path add up to O(n), but all copies made over the run total O(n log n); the tree itself is O(n).

Make the middle element the root. Copy the left half and the right half into new arrays and build each subtree from its copy the same way. Because every split is even, the heights of the two sides differ by at most one.

  1. If the array is empty, return null.
  2. Let mid = length / 2 and create a node with nums[mid].
  3. Build the left child from a copy of nums[0 .. mid - 1].
  4. Build the right child from a copy of nums[mid + 1 .. end].
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        int mid = nums.length / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, nums.length));
        return root;
    }
}

2Optimal (divide and conquer on index bounds)

TimeO(n)Every element becomes exactly one node and each call does O(1) work.
SpaceO(log n)The recursion depth is the height of a balanced tree, about log n (the output tree itself is not counted).

Same idea, but describe each half by its index range [lo, hi] instead of copying it. The middle index of the range becomes the node, [lo, mid - 1] builds its left subtree and [mid + 1, hi] its right subtree.

  1. Call build(0, n - 1).
  2. In build(lo, hi): if lo > hi return null.
  3. mid = lo + (hi - lo) / 2; node = new TreeNode(nums[mid]).
  4. node.left = build(lo, mid - 1); node.right = build(mid + 1, hi); return node.
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

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

Edge cases to test

  • One element
  • Two elements: either one may be the root
  • Even length: the middle can be the left or the right of the two centre values
  • All negative values

Hints

Hint 1

Which value should be the root so that both sides get almost the same number of nodes?

Hint 2

Once the root is the middle element, the left half and right half are the same problem again.

Hint 3

Pass index bounds instead of copying the halves.

FAQ

What is the best time complexity for Convert Sorted Array to Binary Search Tree?

Optimal (divide and conquer on index bounds) runs in O(n) time and O(log n) extra space. Every element becomes exactly one node and each call does O(1) work.

Which pattern does Convert Sorted Array to Binary Search Tree use?

It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.

Is there a brute force solution for Convert Sorted Array to Binary Search Tree?

Yes. Recursion with copied halves takes O(n log n) time and O(n log n) space. Make the middle element the root.

Which edge cases should I test for Convert Sorted Array to Binary Search Tree?

One element; Two elements: either one may be the root; Even length: the middle can be the left or the right of the two centre values; All negative values.