Convert Sorted Array to Binary Search Tree

Recursive:

# 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 not nums:
            return None
        midIndex = 0 + (len(nums) - 1 - 0) / 2
        root = TreeNode(nums[midIndex])
        root.left = self.sortedArrayToBST(nums[:midIndex])
        root.right = self.sortedArrayToBST(nums[midIndex + 1:])
        return root
        

Iterative:

# 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 not nums:     # also check corner case first when using iterative method
            return None
    
        stack = []
        midIndex = 0 + (len(nums) - 1 - 0) / 2
        root = TreeNode(nums[midIndex])
        stack.append((root, 0, len(nums) - 1))
        cur = None
        while(stack):
            cur, curStart, curEnd = stack.pop()
            curMidIndex = curStart + (curEnd - curStart) / 2
            rightMidIndex = curMidIndex + 1 + (curEnd - curMidIndex - 1) / 2
            leftMidIndex = curStart + (curMidIndex - 1 - curStart) / 2
            if rightMidIndex > curMidIndex and rightMidIndex <= curEnd:
                right = TreeNode(nums[rightMidIndex])
                stack.append((right, curMidIndex + 1, curEnd))
                cur.right = right  # Don't forget to link the appropriate left and right nodes
            if leftMidIndex < curMidIndex and leftMidIndex >= curStart:
                left = TreeNode(nums[leftMidIndex])
                stack.append((left, curStart, curMidIndex - 1))
                cur.left = left     # Don't forget to link the appropriate left and right nodes
        return root