Algorithm-Day43-Convert-Sorted-Array-To-Binary-Search-Tree-lc-108

Posted on In , Views:

🧩 Problem Description

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

1
2
3
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-3,9,-10,null,5] is one possible height-balanced BST.

💡 Approach: Divide and Conquer (DFS)

  • The middle element of the sorted array becomes the root.
  • Recursively:
    • Left subarray → left subtree
    • Right subarray → right subtree
  • This ensures the tree is balanced because each split halves the problem.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }

    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) return null;

        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);

        node.left = buildBST(nums, left, mid - 1);
        node.right = buildBST(nums, mid + 1, right);

        return node;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — each element is processed exactly once.
  • Space Complexity: O(log n) — recursion depth (balanced tree).

✍️ Summary

  • Classic divide & conquer problem.
  • Key to balance is picking the middle element.
  • Same pattern appears in:
    • lc-109 (Sorted List to BST)
    • lc-1382 (Balance a BST)
    • lc-654 (Max Binary Tree — similar but different pivot choice)

Understanding this pattern is crucial for recursive tree construction problems.