Convert Sorted Array to Binary Search Tree With Minimal Height

Given a sorted (increasing order) array, Convert it to create a binary search tree with minimal height.

Question

Given a sorted (increasing order) array, Convert it to create a binary search tree with minimal height.

Example:

Input: []
Output:  {}
Explanation: The binary search tree is null

Input: [1,2,3,4,5,6,7]
Output:  {4,2,6,1,3,5,7}
Explanation:
A binary search tree with minimal height.

         4
       /   \
      2     6
     / \    / \
    1   3  5   7

Analyzation

Recursion

The key point of a binary tree is that it always takes the middle point as the next node and that is why the average time complexity is O(logn). Therefore, the method will be taking all the middle point as the next node. Firstly, check the tree existence. Secondly, get the mid point (floor) and make the left tree as the left subarray and right tree as the right subarray.

The Code

class Solution:
    """
    @param: A: an integer array
    @return: A tree node
    """
    def sortedArrayToBST(self, A):
        # write your code here
        if not A:
            return None
        
        # get the middle number as the root to minimize the tree depth
        mid = len(A) // 2  # floor
        root = TreeNode(A[mid])
        root.left = self.sortedArrayToBST(A[:mid])
        root.right = self.sortedArrayToBST(A[mid+1:])
        
        return root

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).