Convert Sorted Array to Balanced BST in DSA C++ - Time & Space Complexity

Time Complexity: Convert Sorted Array to Balanced BST

O(n)

Understanding Time Complexity

We want to know how the time to build a balanced binary search tree grows as the input array size increases.

How does the number of steps change when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

TreeNode* sortedArrayToBST(std::vector<int>& nums, int left, int right) {
    if (left > right) return nullptr;
    int mid = left + (right - left) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBST(nums, left, mid - 1);
    root->right = sortedArrayToBST(nums, mid + 1, right);
    return root;
}
    

This code builds a balanced binary search tree by picking the middle element as root and recursively doing the same for left and right parts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls splitting the array and creating nodes.
• How many times: Each element is visited once to create a node, so recursion happens about n times for n elements.

How Execution Grows With Input

Each element leads to one node creation and two recursive calls on smaller parts.

Input Size (n)	Approx. Operations
10	About 10 node creations and recursive calls
100	About 100 node creations and recursive calls
1000	About 1000 node creations and recursive calls

Pattern observation: The number of operations grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the tree grows linearly with the number of elements in the array.

Common Mistake

[X] Wrong: "Because the function calls itself twice, the time complexity is exponential like O(2^n)."

[OK] Correct: Each element is processed only once to create a node, so the total work is proportional to n, not exponential.

Interview Connect

Understanding this helps you explain how recursion can efficiently build balanced trees, a common task in coding interviews.

Self-Check

"What if we changed the input from a sorted array to an unsorted array? How would the time complexity change?"