Convert Sorted List to Binary Search Tree with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nHere\'s the algorithm:\n\n1. Define a helper function called getHeight th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nHere\'s the algorithm:\n\n1. Define a helper function called getHeight that takes a node as input and returns the height of the node\'s subtree.\n\n2. In the getHeight function, recursively calculate the heights of the left and right subtrees of the node.\n\n3. If the difference in heights of the left and right subtrees is greater than 1, then return -1 to indicate that the tree is not balanced.\n\n4. Otherwise, return the height of the node\'s subtree as 1 plus the maximum of the heights of its left and right subtrees.\n\n5. Define a function called isBalanced that takes a node as input and returns a boolean indicating if the node\'s subtree is balanced.\n\n6. In the isBalanced function, if the node is None, then return True to indicate that the subtree is balanced.\n\n7. Otherwise, recursively check if the left and right subtrees of the node are balanced and if the difference in their heights is at most 1.\n\n8. If both subtrees are balanced and their height difference is at most 1, then return True. Otherwise, return False to indicate that the subtree is not balanced.\n\n9. Call the isBalanced function on the root node of the tree and return its result.\n\n# Complexity\n- Time complexity:\nO(n log n) for the worst-case scenario.\n\n- Space complexity:\n O(h) for the worst-case scenario.\n\n# Code\n```\nclass Solution:\n    def isBalanced(self, root: TreeNode) -> bool:\n        def getHeight(node):\n            if node is None:\n                return 0\n            left_height = getHeight(node.left)\n            right_height = getHeight(node.right)\n            if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:\n                return -1\n            return 1 + max(left_height, right_height)\n        return getHeight(root) != -1\n\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'Python3']