Convert Sorted Array to Binary Search Tree Solution Explained

Data Structures / Tree

Convert Sorted Array to Binary Search Tree

Easy

Given an integer array nums where the elements are sorted in ascending order, convert it to 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.

Example

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted. Multiple valid answers exist.

Input: nums = [1,3]
Output: [3,1] or [1,null,3] — both are valid height-balanced BSTs.

Explanation

The key insight is that the middle element of a sorted array should be the root of a balanced BST. This ensures roughly equal numbers of elements on both sides, minimizing height.

We use a divide and conquer strategy:

Find the middle element of the current subarray — this becomes the root
Recursively build the left subtree from elements before the middle
Recursively build the right subtree from elements after the middle
Return the root node

This approach naturally creates a height-balanced tree because we're always splitting the array roughly in half. The recursion continues until we have empty subarrays, which become null children.

Idea Map

Start with nums array

Find mid = left + (right - left) / 2

Create root = TreeNode(nums[mid])

Left subtree:
nums[left...mid-1]

Right subtree:
nums[mid+1...right]

Return root

End (base case: left > right → return null)

Complexity Analysis

Time Complexity

O(n) — We visit each element exactly once to create a node. The array access at each step is O(1).

Space Complexity

O(log n) — Recursion stack depth is O(log n) for a balanced tree. Plus O(n) for the output tree itself.

Code


class TreeNode:
Definition for a binary tree node with val, left, and right pointers.
    def __init__(self, val=0, left=None, right=None):
Constructor initializes node with a value and optional left/right children.
        self.val = val
Store the node's value.
        self.left = left
Reference to left child node.
        self.right = right
Reference to right child node.

class Solution:
Solution class containing the conversion method.
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
Main function that takes sorted array and returns root of balanced BST.

    def helper(left, right):
Helper function to recursively build BST from subarray nums[left:right+1].
        if left > right:
Base case: empty subarray means no nodes to create, return None.
            return None
Return None for empty subtree.

        mid = (left + right) // 2
Find middle index using integer division. Always choose left-middle for even-length arrays.
        root = TreeNode(nums[mid])
Create root node with middle element as value.

        root.left = helper(left, mid - 1)
Recursively build left subtree from elements before mid.
        root.right = helper(mid + 1, right)
Recursively build right subtree from elements after mid.

        return root
Return the root of this subtree.

    return helper(0, len(nums) - 1)
Start recursion with the full array range.


class TreeNode {
Definition for a binary tree node.
    int val;
Node's integer value.
    TreeNode left;
Reference to left child.
    TreeNode right;
Reference to right child.
    TreeNode() {}
Default constructor.
    TreeNode(int val) { this.val = val; }
Constructor with value only.
    TreeNode(int val, TreeNode left, TreeNode right) {
Full constructor with value and children.
        this.val = val;
Set the node's value.
        this.left = left;
Set left child reference.
        this.right = right;
Set right child reference.
    }
End of constructor.
}
End of TreeNode class.

class Solution {
Solution class with conversion method.
    public TreeNode sortedArrayToBST(int[] nums) {
Main method taking sorted array and returning BST root.
        return helper(nums, 0, nums.length - 1);
Start recursive helper with full array bounds.
    }
End of main method.

    private TreeNode helper(int[] nums, int left, int right) {
Helper method to build BST from subarray.
        if (left > right) return null;
Base case: empty subarray returns null.

        int mid = left + (right - left) / 2;
Find middle index. Using this formula prevents integer overflow.
        TreeNode root = new TreeNode(nums[mid]);
Create root node with middle element.

        root.left = helper(nums, left, mid - 1);
Build left subtree recursively.
        root.right = helper(nums, mid + 1, right);
Build right subtree recursively.

        return root;
Return the constructed subtree root.
    }
End of helper method.
}
End of Solution class.


struct TreeNode {
Definition for a binary tree node using struct.
    int val;
Node's integer value.
    TreeNode *left;
Pointer to left child.
    TreeNode *right;
Pointer to right child.
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
Default constructor using initializer list.
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
Constructor with value only.
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
Full constructor with value and child pointers.
};
End of TreeNode struct.

class Solution {
Solution class definition.
public:
Public access specifier.
    TreeNode* sortedArrayToBST(vector<int>& nums) {
Main method taking vector by reference and returning TreeNode pointer.
        return helper(nums, 0, nums.size() - 1);
Start recursion with full array bounds.
    }
End of main method.

private:
Private access specifier for helper.
    TreeNode* helper(vector<int>& nums, int left, int right) {
Private helper method for recursive construction.
        if (left > right) return nullptr;
Base case: empty subarray returns nullptr.

        int mid = left + (right - left) / 2;
Calculate middle index safely to prevent overflow.
        TreeNode* root = new TreeNode(nums[mid]);
Dynamically allocate new node with middle element.

        root->left = helper(nums, left, mid - 1);
Recursively build left subtree.
        root->right = helper(nums, mid + 1, right);
Recursively build right subtree.

        return root;
Return the constructed subtree root.
    }
End of helper method.
};
End of Solution class.

Edge Cases & Common Mistakes

⚠️

Integer overflow when calculating mid

Using (left + right) / 2 can overflow for very large arrays. Use left + (right - left) / 2 instead.

💡

Multiple valid answers

For even-length arrays, choosing left-middle or right-middle both produce valid balanced BSTs. The problem accepts any valid answer.

✓

Empty array handling

Always check the base case left > right to handle empty subarrays gracefully.

What is a Binary Search Tree?

A Binary Search Tree (BST) is a rooted binary tree where for each node, all elements in its left subtree are smaller, and all elements in its right subtree are larger. This property enables efficient search, insertion, and deletion operations.

Learn more about binary search trees →

account_tree

Disclaimer: This problem is for educational purposes. Practice the 'Convert Sorted Array to Binary Search Tree' problem on LeetCode.

AlgoExplained.dev