Beats : 94.4% [15/145 Top Interview Question]
Intuition\nfind the mid, and add it as the root node, continue...\n\n# Approach\nTwo approaches recursive and iterative both have same time and space complexity
# Intuition\n*find the mid, and add it as the root node, continue...*\n\n# Approach\n*Two approaches recursive and iterative both have same time and space complexity*\n\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n```\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\n\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        if not nums:\n            return None\n        \n        n = len(nums)\n        root = TreeNode()\n        stack = [(0, n, root)]\n        \n        while stack:\n            i, j, node = stack.pop()\n            mid = (i + j) // 2\n            node.val = nums[mid]\n            \n            if mid > i:\n                node.left = TreeNode()\n                stack.append((i, mid, node.left))\n            if mid+1 < j:\n                node.right = TreeNode()\n                stack.append((mid+1, j, node.right))\n                \n        return root\n\n```\n# Iterative Approach\nThe code above  defines a binary tree structure and a function to create a binary search tree from a sorted array of integers.\n\nIn the TreeNode class, there are three instance variables:\n- `val`: represents the value stored in the node.\n- `left`: represents the left child node of the current node.\n- `right`: represents the right child node of the current node.\n\nThe `__init__` method initializes these three instance variables with default values of `0`, `None`, and `None`.\n\nThe Solution class contains a single method, `sortedArrayToBST`, which takes a list of integers `nums` as input and returns a TreeNode object that represents a balanced binary search tree.\n\nIf `nums` is an empty list, the function returns `None`.\n\nOtherwise, it initializes a variable `n` with the length of `nums`, and creates a new TreeNode object called `root` without any value.\n\nIt initializes a stack of tuples containing three values:\n- `i`: represents the starting index of the range of indices to consider.\n- `j`: represents the ending index of the range of indices to consider.\n- `node`: represents the current node.\n\nThe `while` loop runs as long as the `stack` is not empty. In each iteration, it pops the last tuple from the stack, and assigns its values to the variables `i`, `j`, and `node`.\n\nIt calculates the middle index of the range as `(i + j) // 2`, and assigns it to the variable `mid`.\n\nIt assigns the value `nums[mid]` to the `val` instance variable of the `node`.\n\nIf the middle index `mid` is greater than the starting index `i`, it creates a new TreeNode object for the left child of the `node`, assigns it to the `left` instance variable of the `node`, and appends a tuple containing the indices `i`, `mid`, and the new left node to the `stack`.\n\nSimilarly, if the middle index plus one `mid+1` is less than the ending index `j`, it creates a new TreeNode object for the right child of the `node`, assigns it to the `right` instance variable of the `node`, and appends a tuple containing the indices `mid+1`, `j`, and the new right node to the `stack`.\n\nFinally, the function returns the `root` node of the binary search tree.\n\n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n        if not nums:return None\n        mid = len(nums) // 2\n        root = TreeNode(nums[mid])\n        root.left = self.sortedArrayToBST(nums[:mid])\n        root.right = self.sortedArrayToBST(nums[mid+1:])\n        return root\n```\n# Recursive Approach\nThis is another implementation of the `sortedArrayToBST` function to create a binary search tree from a sorted array of integers.\n\nThis implementation is using `recursion`, but it creates a sub-tree for each half of the array, and sets it as the left and right child nodes of the root. The advantage of this implementation is that it is more concise and easier to understand than the `previous implementation that used a stack-based approach`.\n\nThe function takes a list of integers `nums` as input and returns a TreeNode object that represents a balanced binary search tree.\n\nIf `nums` is an empty list, the function returns `None`.\n\nOtherwise, it calculates the middle index of the array `nums` as `mid = len(nums) // 2`.\n\nIt creates a new TreeNode object called `root` with the value `nums[mid]`.\n\nIt recursively calls the `sortedArrayToBST` function to create the left and right sub-trees of the `root`.\n\nFor the left sub-tree, it passes the slice of the `nums` list from the beginning up to but not including the `mid` index.\n\nFor the right sub-tree, it passes the slice of the `nums` list from the `mid+1` index up to the end of the list.\n\nFinally, the function returns the `root` node of the binary search tree.\n
['Python3']