Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0108 - Convert Sorted Array to Binary Search Tree
    0108 - Convert Sorted Array to Binary Search Tree
    0108 - Convert Sorted Array to Binary Search Tree
    0108 - Convert Sorted Array to Binary Search Tree

    0108 - Convert Sorted Array to Binary Search Tree

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

    Solution 1 - Recursive Mid-Point Approach

    Given a sorted array, pick the middle element as the root to ensure the tree is height-balanced. Recursively build the left subtree from the left half and the right subtree from the right half.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(log⁡n)SpaceComplexity: O(\log n)SpaceComplexity:O(logn)

    Solution 2 - Iterative with Stack

    Use a stack to simulate the recursion. Each stack entry holds a node and the subarray bounds (left, right). Process entries by computing the mid-point, assigning the value, and pushing child ranges onto the stack.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 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()