Why Convert Sorted Array to Balanced BST in DSA Python?

The Big Idea

What if you could turn a long, slow list into a fast-searching tree with just a simple trick?

The Scenario

Imagine you have a long list of names sorted alphabetically. You want to organize them so you can quickly find any name, but you only have a simple list. Searching through it one by one takes too long.

The Problem

Looking for a name in a long list means checking each name one after another. This is slow and frustrating, especially if the list is very long. Also, if you try to organize the list manually into a tree, it's easy to make mistakes and end up with an unbalanced tree that slows down searches.

The Solution

Converting the sorted list into a balanced tree automatically splits the list in the middle, making the tree balanced. This means each search cuts the list roughly in half, making finding names much faster and easier without manual effort.

Before vs After

✗ Before

def search_in_list(names, target):
    for name in names:
        if name == target:
            return True
    return False

✓ After

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def sorted_array_to_bst(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_bst(nums[:mid])
    root.right = sorted_array_to_bst(nums[mid+1:])
    return root

What It Enables

This lets you build a fast search tree from a sorted list, making lookups quick and efficient every time.

Real Life Example

Think of a phone book app that quickly finds a contact's number by organizing all contacts into a balanced tree from the sorted list of names.

Key Takeaways

Manual searching in a sorted list is slow and inefficient.

Balanced BST built from sorted array speeds up search by splitting data evenly.

Automatic conversion avoids errors and keeps the tree balanced for fast lookups.

Practice

1. What is the main goal when converting a sorted array to a balanced Binary Search Tree (BST)?

easy

A. To create a BST with minimal height

B. To create a linked list from the array

C. To reverse the array elements

D. To sort the array again

Solution

1. Step 1: Understand the problem goal

   The goal is to convert a sorted array into a BST that is balanced, meaning the tree height is minimized for efficient operations.

2. Step 2: Reason about balanced BST

   A balanced BST has roughly equal nodes on left and right subtrees, which reduces height and improves search time.

3. Final Answer:

   To create a BST with minimal height -> Option A

4. Quick Check:

   Balanced BST = minimal height [OK]

Hint: Pick option about minimal height balanced BST [OK]

Common Mistakes:

• Thinking the array is reversed
• Confusing BST with linked list
• Ignoring balance and height

2. Which of the following Python function signatures is correct for converting a sorted array nums to a balanced BST using recursion?

easy

A. def sortedArrayToBST(nums: list) -> int:

B. def sortedArrayToBST(nums: int) -> TreeNode:

C. def sortedArrayToBST(nums: list[int]) -> Optional[TreeNode]:

D. def sortedArrayToBST(nums: list[int]) -> list[int]:

Solution

1. Step 1: Check parameter type

   The input is a sorted array, so nums should be a list of integers: list[int].

2. Step 2: Check return type

   The function returns the root of a BST, which is a TreeNode or None, so Optional[TreeNode] is correct.

3. Final Answer:

   def sortedArrayToBST(nums: list[int]) -> Optional[TreeNode]: -> def sortedArrayToBST(nums: list[int]) -> Optional[TreeNode]:

4. Quick Check:

   Input list[int], output Optional[TreeNode] [OK]

Hint: Look for list input and TreeNode output signature [OK]

Common Mistakes:

• Using int instead of list[int] for input
• Returning int or list instead of TreeNode
• Missing Optional for possible None return

3. What is the output tree structure (inorder traversal) after running this code?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sortedArrayToBST(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    return root

root = sortedArrayToBST([-10, -3, 0, 5, 9])

# Inorder traversal function
def inorder(node):
    return inorder(node.left) + [node.val] + inorder(node.right) if node else []

print(inorder(root))

medium

A. [0, -10, -3, 5, 9]

B. [-10, -3, 0, 5, 9]

C. [9, 5, 0, -3, -10]

D. [5, 9, 0, -3, -10]

Solution

1. Step 1: Understand inorder traversal

   Inorder traversal of a BST returns the sorted array in ascending order.

2. Step 2: Trace the code output

   The code builds a balanced BST from the sorted array, so inorder traversal returns the original sorted array: [-10, -3, 0, 5, 9].

3. Final Answer:

   [-10, -3, 0, 5, 9] -> Option B

4. Quick Check:

   Inorder traversal = sorted array [OK]

Hint: Inorder traversal of BST equals sorted array [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Expecting reversed or shuffled output
• Not understanding recursion splits

4. Identify the error in this code snippet for converting a sorted array to a balanced BST:

def sortedArrayToBST(nums):
    if len(nums) == 0:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[mid+1:])
    root.right = sortedArrayToBST(nums[:mid])
    return root

medium

A. TreeNode initialization missing value

B. Mid index calculation is incorrect

C. Base case condition is wrong

D. Left and right subtree slices are swapped

Solution

1. Step 1: Check subtree assignments

   The left subtree should be built from elements before mid: nums[:mid], and right subtree from elements after mid: nums[mid+1:].

2. Step 2: Identify swapped slices

   The code assigns left subtree from nums[mid+1:] and right subtree from nums[:mid], which is reversed.

3. Final Answer:

   Left and right subtree slices are swapped -> Option D

4. Quick Check:

   Left subtree = nums[:mid], right subtree = nums[mid+1:] [OK]

Hint: Remember left subtree < mid, right subtree > mid [OK]

Common Mistakes:

• Swapping left and right subtree slices
• Incorrect base case check
• Wrong mid index calculation

5. Given a sorted array with duplicate values [1, 2, 2, 3, 4, 4, 5], which approach correctly builds a balanced BST that includes all duplicates?

hard

A. Always pick leftmost element as root to handle duplicates

B. Remove duplicates first, then build BST

C. Use middle element as root, recursively build left and right subtrees including duplicates

D. Build BST by inserting elements one by one from left to right

Solution

1. Step 1: Understand duplicates in sorted array

   Duplicates appear consecutively; to keep all, do not remove them before building BST.

2. Step 2: Balanced BST construction with duplicates

   Picking the middle element as root and recursively building left and right subtrees preserves duplicates and balance.

3. Final Answer:

   Use middle element as root, recursively build left and right subtrees including duplicates -> Option C

4. Quick Check:

   Middle element root keeps duplicates balanced [OK]

Hint: Keep duplicates, use middle element recursively [OK]

Common Mistakes:

• Removing duplicates before building BST
• Picking always leftmost element as root
• Inserting elements one by one causing imbalance