Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree - Problem

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 1.

Input & Output

Example 1 — Basic Case

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

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

💡 Note: Middle element 0 becomes root. Left subtree from [-10,-3] has root -3 with left child -10. Right subtree from [5,9] has root 9 with left child 5.

Example 2 — Even Length Array

$ Input: nums = [1,3]

› Output: [3,1]

💡 Note: For even length, we pick right middle (index 1). Element 3 becomes root with left child 1.

Example 3 — Single Element

$ Input: nums = [0]

› Output: [0]

💡 Note: Single element becomes the root with no children.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums is sorted in strictly increasing order

Visualization

Tap to expand

Understanding the Visualization

Sorted Array

Input array in ascending order

Pick Middle

Choose middle element as root for balance

Balanced BST

Recursively built balanced binary search tree

Key Takeaway

🎯 Key Insight: Always choose the middle element as root to maintain perfect balance

Asked in

f Facebook 45 a Amazon 38 G Google 32 M Microsoft 28

The key insight is to use divide and conquer: pick the middle element as root to ensure balance. The optimal approach recursively builds left and right subtrees from the corresponding halves. Time: O(n), Space: O(log n).

Common Approaches

Approach	Time	Space	Notes
✓ Sequential Construction	O(n²)	O(n)	Build tree by inserting elements one by one from left to right
Divide and Conquer (Optimal)	O(n)	O(log n)	Recursively pick middle element as root to build balanced BST

Sequential Construction — Algorithm Steps

Start with empty tree
Insert each element from array sequentially
Each insertion maintains BST property

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Empty

Begin with no tree

Insert Sequentially

Add each element following BST rules

Unbalanced Result

Tree becomes like a linked list

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void insertNode(struct TreeNode* root, int val) {
    if (val < root->val) {
        if (root->left) {
            insertNode(root->left, val);
        } else {
            root->left = createNode(val);
        }
    } else {
        if (root->right) {
            insertNode(root->right, val);
        } else {
            root->right = createNode(val);
        }
    }
}

struct TreeNode* solution(int* nums, int numsSize) {
    if (numsSize == 0) return NULL;
    
    struct TreeNode* root = createNode(nums[0]);
    for (int i = 1; i < numsSize; i++) {
        insertNode(root, nums[i]);
    }
    return root;
}

void printTreeArray(struct TreeNode* root) {
    if (!root) {
        printf("[]\n");
        return;
    }
    
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    int values[1000];
    int count = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        if (node) {
            values[count++] = node->val;
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        }
    }
    
    printf("[");
    for (int i = 0; i < count; i++) {
        if (i > 0) printf(",");
        printf("%d", values[i]);
    }
    printf("]\n");
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token) {
            nums[numsSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    struct TreeNode* result = solution(nums, numsSize);
    printTreeArray(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each of n insertions takes O(n) time in worst case due to unbalanced tree

⚠ Quadratic Growth

Space Complexity

O(n)

Tree nodes require O(n) space, recursion stack is O(n) deep

⚡ Linearithmic Space

311.5K Views

Medium Frequency

~15 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sequential Construction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler