Convert Sorted Array to Binary Search Tree

Patrick Leaton

Published: April 13, 2021, 11:16 p.m.

Problem 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.

Example:

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

The description was taken from https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/.

Problem Solution

#O(N) Time, O(N) Space for the Output Tree

class Solution:

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

return self.setNode(0, len(nums) - 1, nums)

def setNode(self, left:int, right:int, nums:list) -> TreeNode:

if left > right:

return None

mid = (left + right) // 2

node = TreeNode(nums[mid])

node.left = self.setNode(left, mid - 1, nums)

node.right = self.setNode(mid + 1, right, nums)

return node

Problem Explanation

A binary search tree has the property of each greater node being placed on the right side of the root, and each lesser node being placed on the left.

If we were to just place each element from a sorted list into a tree, we would end up with a weird linked list. We need to pick the middle node of a sorted list to be the root and then pick the middle node on the left and right side to be the root's children.

We can solve this problem by performing a preorder traversal, recursively setting the middle element of the array partition as each node, and then calling the function on the left and right children.

We will start by creating the setNode helper function.

def setNode(self, left:int, right:int, nums:list) -> TreeNode:

During each call, if the left pointer is greater than the right pointer, then we have run out of elements to set a node with from the current array partition.

We will return none if this is the case.

if left > right:

return None

Otherwise, we will calculate the current middle value from the mean of the current call's left and right pointers.

We will then create a node using the element at the middle index.

mid = (left + right) // 2

node = TreeNode(nums[mid])

Once we have created our node, we will call the function on the left and right children.

The left child will be chosen using the array partition between the left pointer and one index to the left of the middle index.

The right child will be chosen using the partition between one index to the right of the middle index and the right pointer.

We don't include the middle element because we already have it set as a node.

node.left = self.setNode(left, mid - 1, nums)

node.right = self.setNode(mid + 1, right, nums)

Once values are returned from the previous function calls, we will return our current call's node.

return node

Now that we have our helper function made, all there it is to do is make the initial call within the sortedArrayToBST function.

We will pass the input array, its first index as the left pointer, and its last index as the right pointer.

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

return self.setNode(0, len(nums) - 1, nums)