""" 0108.1 - Convert Sorted Array to Binary Search Tree - Solution 1 - Recursive Mid-Point Approach """
#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
"""Convert Sorted Array to BST Function"""
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
#####################################################################################
# Functions
#####################################################################################
def inorder(node):
"""Helper to print inorder traversal"""
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
def testcase():
"""Test Function"""
tree1 = Solution().sortedArrayToBST([-10, -3, 0, 5, 9])
print(inorder(tree1)) # [-10, -3, 0, 5, 9]
tree2 = Solution().sortedArrayToBST([1, 3])
print(inorder(tree2)) # [1, 3]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0108.2 - Convert Sorted Array to Binary Search Tree - Solution 2 - Iterative with Stack """
#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
"""Convert Sorted Array to BST Function"""
if not nums:
return None
root = TreeNode(0)
stack = [(root, 0, len(nums) - 1)]
while stack:
node, left, right = stack.pop()
mid = (left + right) // 2
node.val = nums[mid]
if left <= mid - 1:
node.left = TreeNode(0)
stack.append((node.left, left, mid - 1))
if mid + 1 <= right:
node.right = TreeNode(0)
stack.append((node.right, mid + 1, right))
return root
#####################################################################################
# Functions
#####################################################################################
def inorder(node):
"""Helper to print inorder traversal"""
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
def testcase():
"""Test Function"""
tree1 = Solution().sortedArrayToBST([-10, -3, 0, 5, 9])
print(inorder(tree1)) # [-10, -3, 0, 5, 9]
tree2 = Solution().sortedArrayToBST([1, 3])
print(inorder(tree2)) # [1, 3]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
