Convert Sorted Array to Binary Search Tree

Data Structures and Algorithms

Statement

Given an integer array s that’s sorted in ascending order, construct a height balanced binary search tree (BST) from the array.

Constraints

• 1 ≤ s.length() ≤ 10³
• -10⁴ ≤ s[i] ≤ 10⁴
• s is sorted in strictly ascending order

Solution

"""
production algorithm
"""

from data_structures.binary_tree.binary_tree import BinaryTreeNode


class Solution:
    def sorted_array_to_bst(self, numbers):
        """
        time complexity O(n)
        space complexity O(logn)
        """
        low, high = 0, len(numbers) - 1
        return self.sorted_array_to_bst_helper(numbers, low, high)

    def sorted_array_to_bst_helper(self, numbers, low, high):
        """
        time complexity O(n)
        space complexity O(logn)
        """
        if high < low:
            return None
        mid = low + (high - low) // 2
        root = BinaryTreeNode(numbers[mid])
        root.left = self.sorted_array_to_bst_helper(numbers, low, mid - 1)
        root.right = self.sorted_array_to_bst_helper(numbers, mid + 1, high)
        return root

"""
unit tests
"""

from unittest import TestCase
from algorithms.dfs.convert_sorted_array_to_binary_search_tree.solution import Solution


class SolutionTestCase(TestCase):
    def test_sorted_array_to_bst(self):
        # Given
        array = [-19, -18, -12, -10, -8, -6, -4, -3,
                 -2, 0, 1, 3, 4, 6, 7, 9, 11, 14, 15, 17]
        solution = Solution()

        # When
        result = solution.sorted_array_to_bst(array)

        # Then
        self.assertEqual(result.data, 0)
        self.assertEqual(result.left.data, -8)
        self.assertEqual(result.right.data, 7)
        self.assertEqual(result.left.left.data, -18)
        self.assertEqual(result.left.right.data, -4)
        self.assertEqual(result.right.left.data, 3)
        self.assertEqual(result.right.right.data, 14)
        self.assertEqual(result.left.left.left.data, -19)
        self.assertEqual(result.left.left.right.data, -12)
        self.assertEqual(result.left.right.left.data, -6)
        self.assertEqual(result.left.right.right.data, -3)
        self.assertEqual(result.right.left.left.data, 1)
        self.assertEqual(result.right.left.right.data, 4)
        self.assertEqual(result.right.right.left.data, 9)
        self.assertEqual(result.right.right.right.data, 15)
        self.assertEqual(result.left.left.right.right.data, -10)
        self.assertEqual(result.left.right.right.right.data, -2)
        self.assertEqual(result.right.left.right.right.data, 6)
        self.assertEqual(result.right.right.left.right.data, 11)
        self.assertEqual(result.right.right.right.right.data, 17)

Strategy

Depth First Search.

Explanation

The algorithm is a divide-and-conquer algorithm. Given a subarray, it finds the middle index, creates a binary search tree node with the data at the index, then assigns left and right subtrees to the node with the left and right subarray from the index. The result is a balanced binary search tree.

Time Complexity

The algorithm visits every index of the array once. Therefore, the time complexity of the algorithm is O(n).

Space Complexity

The result of the algorithm is a balanced binary search tree. The algorithm recurses to the height of the binary search tree. The height of a balanced binary search tree is O(logn), where n is the number of nodes in the tree. Therefore, the auxiliary space complexity of the algorithm is O(logn).

Links

data_structures_algorithms/algorithms/dfs/convert_sorted_array_to_binary_search_tree at main ·…