Convert Sorted Array to Balanced BST in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced BST Inorder Traversal

Given a sorted array, a balanced binary search tree (BST) is created by picking the middle element as root and recursively doing the same for left and right subarrays. What is the inorder traversal output of the BST created from the array [1, 2, 3, 4, 5]?

DSA Python

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

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

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

root = sorted_array_to_bst([1, 2, 3, 4, 5])
print(inorder(root))

A [1, 2, 3, 4, 5]

B [3, 2, 1, 4, 5]

C [5, 4, 3, 2, 1]

D [2, 1, 3, 4, 5]

💡 Hint

Inorder traversal of a BST always returns the sorted order of elements.

The inorder traversal of a BST visits nodes in ascending order. Since the BST is built from a sorted array, the inorder traversal returns the original sorted array.

🧠 Conceptual

intermediate

Height of Balanced BST from Sorted Array

If you create a balanced BST from a sorted array of length 15 by always choosing the middle element as root, what is the height of the resulting BST? (Height is the number of edges on the longest path from root to a leaf.)

A 4

B 5

C 3

D 6

💡 Hint

A balanced BST from n nodes has height about log2(n).

For 15 nodes, height is floor(log2(15)) = 3 edges (4 levels).

🔧 Debug

advanced

Identify the Bug in BST Construction Code

What error will this code produce when converting a sorted array to a balanced BST? ```python class Node: def __init__(self, val): self.val = val self.left = None self.right = None def sorted_array_to_bst(arr): if len(arr) == 0: return None mid = len(arr) // 2 root = Node(arr[mid]) root.left = sorted_array_to_bst(arr[mid+1:]) root.right = sorted_array_to_bst(arr[:mid]) return root root = sorted_array_to_bst([1, 2, 3]) print(root.val) ```

A The tree is constructed but left and right children are swapped, no error.

B IndexError due to slicing beyond array bounds.

C RecursionError due to infinite recursion.

D TypeError because of wrong data type in Node.

💡 Hint

Check the slices used for left and right subtrees.

The code swaps left and right subtree slices, so the tree is built incorrectly but no runtime error occurs.

❓ Predict Output

advanced

Output of Level Order Traversal of Balanced BST

What is the output of the level order traversal (breadth-first) of the balanced BST created from the sorted array [10, 20, 30, 40, 50, 60, 70]?

DSA Python

from collections import deque

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

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

def level_order(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

root = sorted_array_to_bst([10, 20, 30, 40, 50, 60, 70])
print(level_order(root))

A [10, 20, 30, 40, 50, 60, 70]

B [40, 20, 60, 10, 30, 50, 70]

C [30, 20, 10, 40, 50, 60, 70]

D [70, 60, 50, 40, 30, 20, 10]

💡 Hint

Level order visits nodes level by level from left to right.

The middle element 40 is root, left subtree root 20, right subtree root 60, and so on, producing the level order [40, 20, 60, 10, 30, 50, 70].

🧠 Conceptual

expert

Minimum Number of Nodes for Given Height in Balanced BST

What is the minimum number of nodes in a balanced binary search tree of height 4 (edges)?

A 16

B 15

C 8

D 31

💡 Hint

A balanced BST of height h has at least 2^h nodes.

Height 4 means 5 levels (0 to 4). Minimum nodes in a balanced BST is 2^(height+1) - 1 = 2^5 - 1 = 31.

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