:orphan:

Convert Sorted Array to Binary Search Tree
==========================================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Given an integer array ``nums`` where the elements are sorted in
**ascending order**, convert *it to a* height-balanced *binary search
tree*.

 

**Example 1:**

|image1|

::


   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:

**Example 2:**

|image2|

::


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

 

**Constraints:**

- ``1 <= nums.length <= 10``\ :sup:```4```
- ``-10``\ :sup:```4```\ ``<= nums[i] <= 10``\ :sup:```4```
- ``nums`` is sorted in a **strictly increasing** order.

.. |image1| image:: https://assets.leetcode.com/uploads/2021/02/18/btree1.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2021/02/18/btree.jpg

.. highlight:: python

Pattern
-------
Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree

Solution
--------
A balanced binary tree will have the middle element of ``nums`` as the root,
the 1/4 and 3/4 elements as the left and right children, and so on. Find the
middle element of ``nums`` and divide ``nums`` into two halves. Repeat on the
left half to form the left subtree and the right half to form the right subtree.

Code
----

.. literalinclude:: ../problems/easy/convert-sorted-array-to-binary-search-tree/convert_sorted_array_to_binary_search_tree__approach_1.py
    :language: python
    :lines: 11-

Test
----
>>> from convert_sorted_array_to_binary_search_tree__approach_1 import sortedArrayToBST, tree2list
>>> root = sortedArrayToBST([-10, -3, 0, 5, 9])
>>> tree2list(root)
[0, -3, -10, 9, 5]
>>> root = sortedArrayToBST([1, 3])
>>> tree2list(root)
[3, 1]

Complexity
----------
| :math:`n` is the length of the input array.
| Time: :math:`O(n)` — visit every element
| Auxiliary Space: :math:`O(1)`

.. autoclass:: convert_sorted_array_to_binary_search_tree__approach_1.TreeNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: convert_sorted_array_to_binary_search_tree__approach_1.sortedArrayToBST

.. autofunction:: convert_sorted_array_to_binary_search_tree__approach_1.tree2list