Teaching Kids Programming – Recursive Algorithm to Convert a Sorted List to a Balanced Binary Search Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a sorted (increasing order) array with unique integer elements, write an algo­rithm to create a binary search tree with minimal height.

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

One possible answer is: [0,-3,9,-10,null,5]，which represents the following tree:

          0 
         / \ 
       -3   9 
       /   / 
     -10  5 

Recursive Algorithm to Convert a Sorted List to a Balanced Binary Search Tree

A Balanced Binary Tree should have no more than 1 depth difference for any two sub trees. Given the sorted list, if we divide into half, the two parts (used to construct the left and right tree respectively), should have no more difference than 1. In this case, the balanced binary search tree is also the minimal height BST.

So, recursively, we pick the current middle as the current root, and recursively construct its left, and right subtrees.

The time complexity is O(N) where N is the number of the nodes in the sorted list – and also the number of the nodes in the final balanced binary search tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if len(nums) == 0:
            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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if len(nums) == 0:
            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

See also: Recursive Algorithm to Convert a List to Binary Search Tree

–EOF (The Ultimate Computing & Technology Blog) —