Convert Sorted Array to Balanced BST in DSA Python - Build from Scratch

Convert Sorted Array to Balanced BST

📖 Scenario: Imagine you have a sorted list of numbers representing book IDs in a library. You want to organize these IDs into a balanced tree structure so that searching for any book ID is fast and efficient.

🎯 Goal: Build a balanced Binary Search Tree (BST) from a sorted array of integers. The BST should be balanced, meaning the left and right subtrees of every node differ in height by no more than one.

📋 What You'll Learn

Create a sorted list called sorted_array with the exact values: [10, 20, 30, 40, 50, 60, 70]

Create a class called TreeNode with attributes val, left, and right

Write a function called sorted_array_to_bst that takes sorted_array and returns the root of a balanced BST

Print the BST nodes in in-order traversal to verify the tree structure

💡 Why This Matters

🌍 Real World

Balanced BSTs are used in databases and file systems to keep data sorted and allow fast search, insert, and delete operations.

💼 Career

Understanding how to build and traverse trees is essential for software engineers working with data structures, algorithms, and system design.

1

Create the sorted array

Create a list called sorted_array with these exact values: [10, 20, 30, 40, 50, 60, 70]

DSA Python

# Create the sorted_array list with the given values
# Your code here

Hint

Use square brackets to create a list and separate numbers with commas.

2

Define the TreeNode class

Define a class called TreeNode with an __init__ method that takes val and sets self.val, self.left, and self.right to None

DSA Python

sorted_array = [10, 20, 30, 40, 50, 60, 70]

# Define the TreeNode class below
# Your code here

Hint

Define a class with class TreeNode: and an __init__ method that sets the value and initializes left and right children to None.

3

Write the function to convert sorted array to balanced BST

Write a function called sorted_array_to_bst that takes nums as input and returns the root of a balanced BST. Use recursion to pick the middle element as root, then build left and right subtrees from the left and right halves of the array.

DSA Python

sorted_array = [10, 20, 30, 40, 50, 60, 70]

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

# Define the sorted_array_to_bst function below
# Your code here

Hint

Use the middle element as root, recursively build left subtree from left half, right subtree from right half.

4

Print the BST in in-order traversal

Write a function called inorder_traversal that takes root and prints the node values in in-order (left, root, right). Then call inorder_traversal with the BST created from sorted_array.

DSA Python

sorted_array = [10, 20, 30, 40, 50, 60, 70]

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

# Define inorder_traversal function and print the BST values
# Your code here

Hint

In-order traversal prints nodes in ascending order for BST. Use recursion to visit left child, print root, then right child.

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