# Convert Sorted Array to Binary Search Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/convert-sorted-array-to-binary-search-tree
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Tree, Binary Tree, Binary Search Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Airbnb](https://scaleengineer.com/companies/airbnb), [Apple](https://scaleengineer.com/companies/apple), [Meta](https://scaleengineer.com/companies/meta), [Samsung](https://scaleengineer.com/companies/samsung)
---
## Problem
Given an integer array `nums` where the elements are sorted in **ascending order**, convert _it to a_ **_height-balanced_** _binary search tree_.

**Example 1:**

![](https://assets.glich.co/dsa/convert-sorted-array-to-binary-search-tree/image0.jpg) 

**Input:** nums = [-10,-3,0,5,9]
**Output:** [0,-3,9,-10,null,5]
**Explanation:** [0,-10,5,null,-3,null,9] is also accepted:
![](https://assets.glich.co/dsa/convert-sorted-array-to-binary-search-tree/image1.jpg)

**Example 2:**

![](https://assets.glich.co/dsa/convert-sorted-array-to-binary-search-tree/image2.jpg) 

**Input:** nums = [1,3]
**Output:** [3,1]
**Explanation:** [1,null,3] and [3,1] are both height-balanced BSTs.

**Constraints:**

* `1 <= nums.length <= 104`
* `-104 <= nums[i] <= 104`
* `nums` is sorted in a **strictly increasing** order.

# Approaches
## Naive Insertion followed by Balancing
This approach first constructs a Binary Search Tree (BST) by inserting elements from the sorted array one by one. Since the array is sorted, this process results in a completely unbalanced, skewed tree (resembling a linked list). Afterwards, a separate balancing algorithm is applied to transform the skewed tree into a height-balanced BST.
**Time:** O(N^2) · **Space:** O(N)
**Pros:** Conceptually simple if you consider building and balancing as two separate, well-known problems.
**Cons:** Extremely inefficient with a time complexity of O(N^2) for building the initial skewed tree.; Fails to meet the 'height-balanced' requirement without a complex and separate balancing algorithm.; Completely ignores the useful property of the input array being pre-sorted, which could be used to build the tree in a balanced way from the start.
### Explanation
The process involves two main phases. First, a BST is built. We start with an empty tree and insert `nums[0]`, then `nums[1]`, and so on. Because `nums[i] > nums[i-1]`, every insertion will traverse down the right side of the tree, resulting in a long chain of right children—a structure often called a 'vine' or a skewed tree. The height of this tree is N, which is far from balanced. The second phase would be to rebalance this tree. While algorithms like DSW exist for this, they add significant complexity. This entire method is counter-intuitive as it creates an unbalanced structure only to fix it later, while the sorted array provides all the information needed to build a balanced tree directly.

Below is the code for the first phase, which demonstrates the creation of the unbalanced tree.
```java
class Solution {
    // This method only demonstrates the flawed initial construction.
    // It does NOT produce a balanced tree as required.
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        // The first element becomes the root.
        TreeNode root = new TreeNode(nums[0]);
        // Insert subsequent elements.
        for (int i = 1; i < nums.length; i++) {
            insert(root, nums[i]);
        }
        // The tree is now a skewed BST and needs a balancing step.
        // This is highly inefficient.
        return root; 
    }

    // Standard iterative BST insert.
    private void insert(TreeNode node, int val) {
        while (true) {
            if (val > node.val) {
                if (node.right == null) {
                    node.right = new TreeNode(val);
                    return;
                }
                node = node.right;
            } else {
                // This case won't be hit with a strictly increasing sorted array.
                if (node.left == null) {
                    node.left = new TreeNode(val);
                    return;
                }
                node = node.left;
            }
        }
    }
}
```
### Algorithm
- Initialize an empty Binary Search Tree (BST).
- Iterate through the sorted `nums` array, inserting each element into the BST using a standard insertion algorithm.
- Since the array is sorted, this creates a right-skewed tree where each new node is a right child of the previous one.
- This tree is a valid BST but is not height-balanced.
- To fulfill the problem's requirement, a subsequent balancing step is needed. An algorithm like the Day-Stout-Warren (DSW) algorithm could be used to transform the skewed tree into a balanced one through a series of rotations.

## Iterative Construction with a Stack
This approach mimics the recursive divide-and-conquer strategy but uses an explicit stack to manage the subproblems, avoiding deep recursion. It iteratively processes ranges of the array to build the tree nodes and link them together. By always choosing the middle of a range for a node, it ensures the final tree is height-balanced.
**Time:** O(N) · **Space:** O(N)
**Pros:** Avoids recursion, which can prevent stack overflow errors for extremely large inputs (though not a concern here given the constraints).; Achieves the optimal time complexity of O(N).
**Cons:** More complex to implement and reason about compared to the recursive solution.; Uses more space (O(N)) than the recursive approach (O(log N)) because it needs to store all pending subproblems explicitly on the stack.
### Explanation
Instead of relying on the program's call stack, we manage our own stack of 'tasks'. Each task consists of a parent node and the array bounds (`left`, `right`) for the subtree we need to build and attach to it. We start by creating the root from the middle of the entire array. Then, we push two tasks onto the stack: one for the root's left child (using the left half of the array) and one for its right child (using the right half). The loop continues to pop tasks, create a child node from the middle of its assigned range, attach it to its parent, and then push two new tasks for the newly created child's own children. This continues until all array elements have been placed in the tree.
```java
import java.util.Stack;

class Solution {
    // Helper class to store state for the iterative approach
    private static class State {
        TreeNode parent;
        int left;
        int right;

        State(TreeNode parent, int left, int right) {
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        int n = nums.length;
        int mid = (n - 1) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        Stack<State> stack = new Stack<>();
        // Push states for the left and right subtrees of the root
        stack.push(new State(root, 0, mid - 1));
        stack.push(new State(root, mid + 1, n - 1));

        while (!stack.isEmpty()) {
            State currentState = stack.pop();
            TreeNode parent = currentState.parent;
            int left = currentState.left;
            int right = currentState.right;

            if (left > right) {
                continue;
            }

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

            if (child.val < parent.val) {
                parent.left = child;
            } else {
                parent.right = child;
            }

            // Push states for the new child's subtrees
            stack.push(new State(child, left, childMid - 1));
            stack.push(new State(child, childMid + 1, right));
        }
        return root;
    }
}
```
### Algorithm
- Handle the edge case of an empty input array.
- Create the root node from the middle element of the array.
- Use a stack to keep track of nodes that need their children attached, along with the index ranges for their potential left and right subtrees. A helper class or object can store this state: `(parent_node, left_bound, right_bound)`.
- Push the initial states for the root's left and right subtrees onto the stack.
- Loop as long as the stack is not empty.
- In each iteration, pop a state `(parent, left, right)`.
- If `left > right`, there are no elements in this range, so continue.
- Find the middle element `nums[mid]` in the range `[left, right]` and create a new `child` node.
- Attach the `child` to the `parent` as either the left or right child based on its value.
- Push the new subproblems for the `child`'s left and right subtrees onto the stack: `(child, left, mid - 1)` and `(child, mid + 1, right)`.

## Recursive Divide and Conquer
This is the most elegant and efficient approach. It leverages the sorted nature of the array to directly construct a height-balanced BST. The core idea is to select the middle element of the array as the root of the tree, which naturally divides the remaining elements into two equal-sized (or nearly equal-sized) groups. These groups form the left and right subtrees, which are constructed recursively using the same logic.
**Time:** O(N) · **Space:** O(log N)
**Pros:** Optimal time complexity of O(N) as each element is visited once.; Optimal space complexity of O(log N) due to the balanced recursion depth.; The code is clean, concise, and directly reflects the divide-and-conquer logic.; Naturally produces a height-balanced tree by its construction method.
**Cons:** For extremely large N (beyond problem constraints), deep recursion could theoretically lead to a stack overflow, though this is highly unlikely for a balanced tree structure where depth is logarithmic.
### Explanation
This method perfectly embodies the divide-and-conquer paradigm. By choosing the middle element of a sorted range as the root, we guarantee two properties: 1) The BST property is maintained (all elements to the left are smaller, all to the right are larger). 2) The tree remains height-balanced because the number of nodes in the left and right subtrees is as close to equal as possible at every step. The recursion provides a clean way to apply this logic to progressively smaller subarrays until all elements are placed in the tree.

For an array `[-10, -3, 0, 5, 9]`, the process is:
1. Root is `0` (middle of `[-10, -3, 0, 5, 9]`).
2. Left child is the root of `[-10, -3]`, which is `-3`.
3. Right child is the root of `[5, 9]`, which is `9`.
4. The left child of `-3` is `-10`.
5. The left child of `9` is `5`.
This naturally builds a balanced tree.
```java
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int left, int right) {
        // Base case: If the range is invalid, the subtree is empty.
        if (left > right) {
            return null;
        }

        // Find the middle element to make it the root.
        // This ensures the tree is balanced.
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        // Recursively build the left subtree from the left half of the array.
        root.left = buildTree(nums, left, mid - 1);

        // Recursively build the right subtree from the right half of the array.
        root.right = buildTree(nums, mid + 1, right);

        return root;
    }
}
```
### Algorithm
- Define a helper function that takes the array and the `left` and `right` indices of the subarray to process.
- The main function calls this helper with the initial range of the entire array: `(nums, 0, nums.length - 1)`.
- **Base Case:** In the helper function, if `left > right`, it means the current subarray is empty, so return `null`.
- **Recursive Step:**
  - Find the middle index of the current range: `mid = left + (right - left) / 2`.
  - Create a new `TreeNode` with the value `nums[mid]`. This node becomes the root of the current subtree.
  - Recursively call the helper to build the left subtree from the left half of the subarray: `root.left = helper(nums, left, mid - 1)`.
  - Recursively call the helper to build the right subtree from the right half: `root.right = helper(nums, mid + 1, right)`.
  - Return the created `root` node.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private int [] nums ; public TreeNode SortedArrayToBST ( int [] nums ) { this . nums = nums ; return dfs ( 0 , nums . Length - 1 ); } private TreeNode dfs ( int l , int r ) { if ( l > r ) { return null ; } int mid = ( l + r ) >> 1 ; return new TreeNode ( nums [ mid ], dfs ( l , mid - 1 ), dfs ( mid + 1 , r )); } }
```

### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int [] nums ; public TreeNode sortedArrayToBST ( int [] nums ) { this . nums = nums ; return dfs ( 0 , nums . length - 1 ); } private TreeNode dfs ( int l , int r ) { if ( l > r ) { return null ; } int mid = ( l + r ) >> 1 ; TreeNode left = dfs ( l , mid - 1 ); TreeNode right = dfs ( mid + 1 , r ); return new TreeNode ( nums [ mid ], left , right ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[]} nums * @return {TreeNode} */ var sortedArrayToBST =
  function (nums) {
    const dfs = (l, r) => {
      if (l > r) {
        return null;
      }
      const mid = (l + r) >> 1;
      const left = dfs(l, mid - 1);
      const right = dfs(mid + 1, r);
      return new TreeNode(nums[mid], left, right);
    };
    return dfs(0, nums.length - 1);
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * sortedArrayToBST ( vector < int >& nums ) { function < TreeNode * ( int , int ) > dfs = [ & ]( int l , int r ) -> TreeNode * { if ( l > r ) { return nullptr ; } int mid = ( l + r ) >> 1 ; auto left = dfs ( l , mid - 1 ); auto right = dfs ( mid + 1 , r ); return new TreeNode ( nums [ mid ], left , right ); }; return dfs ( 0 , nums . size () - 1 ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def sortedArrayToBST ( self , nums : List [ int ]) -> Optional [ TreeNode ]: def dfs ( l , r ): if l > r : return None mid = ( l + r ) >> 1 left = dfs ( l , mid - 1 ) right = dfs ( mid + 1 , r ) return TreeNode ( nums [ mid ], left , right ) return dfs ( 0 , len ( nums ) - 1 ) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution ( object ): def sortedArrayToBST ( self , nums ): """ :type nums: List[int] :rtype: TreeNode """ if nums : midPos = len ( nums ) / 2 mid = nums [ midPos ] root = TreeNode ( mid ) root . left = self . sortedArrayToBST ( nums [: midPos ]) root . right = self . sortedArrayToBST ( nums [ midPos + 1 :]) return root
```