💬 Discord
Sign In
NeetCode #392LC-108EasyTrees
← Back to All Problems

#392 · #108 · Convert Sorted Array to Binary Search Tree(将有序数组转换为二叉搜索树)

📌 Problem Statement & Constraints

Given an integer array nums sorted in ascending order, convert it to a height-balanced binary search tree. Constraints: 1 <= nums.length <= 10^4, -10^4 <= nums[i] <= 10^4; values are distinct.

💡 Core Algorithmic Approaches

  1. Choosing the middle element as the root guarantees that the left and right subtrees have nearly equal sizes, which is exactly the height-balance condition.
  2. Recurse on the two halves with the same rule.
  3. The base case is an empty range, which returns None.
  4. Because the array is sorted, the in-order traversal of the result reproduces it -- so the BST property is automatic.

💻 Benchmark Python3 Implementation

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def build(lo: int, hi: int) -> Optional[TreeNode]:
            if lo > hi:
                return None                # empty range
            mid = (lo + hi) // 2           # middle -> balanced
            node = TreeNode(nums[mid])
            node.left = build(lo, mid - 1)
            node.right = build(mid + 1, hi)
            return node

        return build(0, len(nums) - 1)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each element becomes exactly one node.
💾 Space Complexity
O(log n) for the recursion stack on a balanced build, plus O(n) for the nodes.

⚠️ Interview Pitfalls & Follow-ups

  • Choosing the first element as the root: the tree would degenerate into a linked list of height n.
  • Slicing the array: it works, but the index-range version avoids O(n log n) total copying.
  • Using mid = (lo + hi + 1) // 2: still balanced, just biased right; either choice is acceptable but be consistent.
  • Assuming duplicates are allowed: values are distinct, which keeps the BST property unambiguous.