What happens if you inserting elements one by one from sorted array?

Creates skewed tree, leading to O(n^2) time and unbalanced BST Fix: Use divide and conquer to pick middle element as root

What happens if you incorrect mid calculation causing infinite recursion?

Stack overflow or infinite loop Fix: Calculate mid as (left + right) // 2 or left + (right - left) // 2

What happens if you not handling base case left > right properly?

Recursion never ends or returns wrong subtree Fix: Return null when left > right

What happens if you using array slicing in recursion?

Extra O(n) space and time overhead per call, inefficient for large inputs Fix: Use indices to pass subarray boundaries instead of slicing

Interview Prepbinary-search-treeseasyAmazonGoogleFacebook

Convert Sorted Array to Height-Balanced BST

Choose your preparation mode3 modes available

Try It Solution Trace

🎯

easyTREEAmazonGoogleFacebook

Imagine you have a sorted list of book IDs and want to organize them in a way that allows quick search and insertion. Creating a balanced binary search tree from this sorted list ensures efficient operations.

💡 This problem is about constructing a balanced binary search tree (BST) from a sorted array. Beginners often struggle because they try to insert elements one by one, which leads to unbalanced trees. Understanding how to pick the middle element as root to maintain balance is key.

📋

Problem Statement

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 defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4nums is sorted in ascending order

💡

Example

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

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

Choosing 0 as root splits array into left [-10, -3] and right [5, 9]. Recursively building subtrees results in a balanced BST. Note: This output is a level order traversal with nulls for missing nodes. In test cases, inorder traversal arrays are used to verify correctness.

Single element array → tree with one node
Two elements array → root and one child
All elements are the same → balanced tree with duplicates allowed
Large array with 10^5 elements → performance and stack depth considerations

⚠️

Common Mistakes

Inserting elements one by one from sorted array

Creates skewed tree, leading to O(n^2) time and unbalanced BST

✅ Use divide and conquer to pick middle element as root

Incorrect mid calculation causing infinite recursion

Stack overflow or infinite loop

✅ Calculate mid as (left + right) // 2 or left + (right - left) // 2

Not handling base case left > right properly

Recursion never ends or returns wrong subtree

✅ Return null when left > right

Using array slicing in recursion

Extra O(n) space and time overhead per call, inefficient for large inputs

✅ Use indices to pass subarray boundaries instead of slicing

Mixing up left and right subtree indices

Incorrect tree structure, failing balance or BST property

✅ Carefully assign left subtree to left..mid-1 and right subtree to mid+1..right

🧠

Brute Force (Insert One by One)

💡 This approach exists to show the naive way of building a BST by inserting elements one by one, which is intuitive but inefficient and leads to unbalanced trees.

Intuition

Insert each element from the sorted array into the BST in order. Since the array is sorted, inserting sequentially creates a skewed tree.

Algorithm

Initialize an empty BST.
Iterate over each element in the sorted array.
Insert the current element into the BST using standard BST insertion.
Return the root of the BST after all insertions.

💡 The difficulty is realizing that inserting sorted elements sequentially creates a skewed tree, not balanced.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert_into_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root

def sorted_array_to_bst(nums):
    root = None
    for num in nums:
        root = insert_into_bst(root, num)
    return root

# Driver code to test
if __name__ == '__main__':
    nums = [-10, -3, 0, 5, 9]
    root = sorted_array_to_bst(nums)
    # Simple inorder traversal to print sorted values
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(root))

Line Notes

class TreeNode:Defines the structure of a BST node with value and left/right children

def insert_into_bst(root, val):Defines recursive insertion function for BST

if not root:Base case: insert new node when reaching null position

if val < root.val:Decide to go left or right based on BST property

root.left = insert_into_bst(root.left, val)Recursively insert in left subtree

for num in nums:Iterate over all elements to insert sequentially

root = insert_into_bst(root, num)Update root after each insertion

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (val < root.val) root.left = insertIntoBST(root.left, val);
        else root.right = insertIntoBST(root.right, val);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = null;
        for (int num : nums) {
            root = insertIntoBST(root, num);
        }
        return root;
    }

    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode root = sol.sortedArrayToBST(nums);
        inorder(root);
    }
}

Line Notes

class TreeNode {Defines BST node structure with value and children

public TreeNode insertIntoBST(TreeNode root, int val) {Recursive insertion method for BST

if (root == null) return new TreeNode(val);Base case: create new node when null reached

if (val < root.val) root.left = insertIntoBST(root.left, val);Insert into left subtree if smaller

for (int num : nums) {Iterate over all elements to insert sequentially

root = insertIntoBST(root, num);Update root after each insertion

public static void main(String[] args) {Driver code entry point

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insertIntoBST(root->left, val);
    else root->right = insertIntoBST(root->right, val);
    return root;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
    TreeNode* root = nullptr;
    for (int num : nums) {
        root = insertIntoBST(root, num);
    }
    return root;
}

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    vector<int> nums = {-10, -3, 0, 5, 9};
    TreeNode* root = sortedArrayToBST(nums);
    inorder(root);
    cout << endl;
    return 0;
}

Line Notes

struct TreeNode {Defines BST node with value and pointers to children

TreeNode* insertIntoBST(TreeNode* root, int val) {Recursive insertion function for BST

if (!root) return new TreeNode(val);Create new node when null reached

if (val < root->val) root->left = insertIntoBST(root->left, val);Insert into left subtree if smaller

for (int num : nums) {Iterate over all elements to insert sequentially

root = insertIntoBST(root, num);Update root after each insertion

int main() {Driver code entry point

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function insertIntoBST(root, val) {
    if (!root) return new TreeNode(val);
    if (val < root.val) root.left = insertIntoBST(root.left, val);
    else root.right = insertIntoBST(root.right, val);
    return root;
}

function sortedArrayToBST(nums) {
    let root = null;
    for (const num of nums) {
        root = insertIntoBST(root, num);
    }
    return root;
}

// Driver code
const nums = [-10, -3, 0, 5, 9];
const root = sortedArrayToBST(nums);

function inorder(node) {
    if (!node) return [];
    return [...inorder(node.left), node.val, ...inorder(node.right)];
}

console.log(inorder(root));

Line Notes

class TreeNode {Defines BST node with value and left/right children

function insertIntoBST(root, val) {Recursive insertion function for BST

if (!root) return new TreeNode(val);Create new node when null reached

if (val < root.val) root.left = insertIntoBST(root.left, val);Insert into left subtree if smaller

for (const num of nums) {Iterate over all elements to insert sequentially

root = insertIntoBST(root, num);Update root after each insertion

console.log(inorder(root));Print inorder traversal to verify BST

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Each insertion takes O(h) time, where h is tree height. Since tree becomes skewed, h can be O(n), so total O(n^2).

💡 For n=20, this means roughly 400 operations, which is inefficient for large inputs.

Interview Verdict: Accepted but inefficient

This approach works but is too slow for large inputs and produces unbalanced trees, so better methods are preferred.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Insert One by One)	`O(n^2)`	`O(n)`	Yes (deep recursion if skewed)	Yes	Mention only - never code
2. Divide and Conquer Recursion	`O(n)`	`O(log n)`	No (balanced recursion depth)	Yes	Code this approach in most interviews
3. Inorder Simulation with Index Pointer	`O(n)`	`O(log n)`	No	Yes	Use for large inputs or when avoiding slicing

Convert Sorted Array to Height-Balanced BST

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems