Leetcode 108. Convert Sorted Array to Binary Search Tree (Python)

Related Topic

Depth-First-Search. Tree.

Description

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Sample I/O

Example 1

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Methodology

This question can be solved by Depth First Search.

To ensure the depth of two substrees of each node never differ by more than one. We will start to use the mid node as root recursively. This will ensure the number of left node and right node for each root is either equal or differ by 1. Since the the input is already sorted. It will be easy to build a binary search tree.

Code 1 (DFS)

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if len(nums) == 0: return None
        
        mid = len(nums)//2
        node = TreeNode(nums[mid])
        
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid+1:])
        return node

BigO

We traversal all nodes of the input so it takes O(n) time complexity