[Python] Easy DFS - Clear explain - Clean & Concise
Idea\n- In a height-balanced BST:\n\t- All elements in the left subtree are less than root.val.\n\t- All elements in the right subtree are greater than root.val
**Idea**\n- In a **height-balanced BST**:\n\t- All elements in the left subtree are less than `root.val`.\n\t- All elements in the right subtree are greater than `root.val`.\n\t- The left subtree is a height-balanced BST.\n\t- The right subtree is a height-balanced BST.\n\t- The difference between the height of the left subtree and the height of the right subtree is at most 1.\n- We need to build BST so that it\'s a **height balanced BST**:\n\t- So we choose `nums[mid]` as the value for our `root`\n\t- Then divide arrays into 2 halfs:\n\t\t- One half from `[left..mid-1]` for building the left subtree.\n\t\t- Other half from `[mid+1..right]` for building the right subtree. \n\t- Repeat the recursion util we\'ve completed build BST from all elements in `nums` array.\n- Since this problem is quite easy, now **I challenge you to solve this problem** instead [109. Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/)\n\n```python\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        def dfs(left, right):\n            if left > right: return None\n            mid = (left + right) // 2\n            root = TreeNode(nums[mid])\n            root.left = dfs(left, mid - 1)\n            root.right = dfs(mid+1, right)\n            return root\n        \n        return dfs(0, len(nums) - 1)\n```\n\n**Complexity**\n- Time: `O(N)`\n- Extra Space (without counting output as space): `O(logN)`
[]