Convert Sorted Array to Balanced BST in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle index of the array.

DSA Python

mid = (start + end) [1] 2

Drag options to blanks, or click blank then click option'

A+

B*

C//

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of // causes wrong index.

Using * or - does not find the middle.

We use integer division (//) to get the middle index as an integer.

2fill in blank

medium

Complete the code to create a new tree node with the middle element.

DSA Python

node = TreeNode([1][mid])

Drag options to blanks, or click blank then click option'

Anums

Blist

Carray

Darr

Attempts:

3 left

💡 Hint

Common Mistakes

Using undefined variable names like arr or list.

Forgetting to index the array.

The input array is named nums, so we use nums[mid] to get the middle element.

3fill in blank

hard

Fix the error in the recursive call to build the left subtree.

DSA Python

node.left = self.sortedArrayToBST([1], start, mid - 1)

Drag options to blanks, or click blank then click option'

Aarray

Barr

Clist

Dnums

Attempts:

3 left

💡 Hint

Common Mistakes

Passing undefined variable names causes errors.

Forgetting to pass the array in recursive calls.

The input array is named nums, so we must pass it in the recursive call.

4fill in blank

hard

Fill both blanks to complete the recursive call for the right subtree.

DSA Python

node.right = self.sortedArrayToBST([1], [2], end)

Drag options to blanks, or click blank then click option'

Anums

Bmid + 1

Cstart

Dmid - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices like start or mid - 1 for the right subtree.

Passing wrong variable names.

We pass the array nums and the new start index mid + 1 to build the right subtree.

5fill in blank

hard

Fill all three blanks to complete the base case and return statement.

DSA Python

if start > [1]:
    return [2]

return [3]

Drag options to blanks, or click blank then click option'

Aend

BNone

Cnode

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variables in the base case condition.

Returning wrong values instead of None or node.

The base case checks if start is greater than end, returns None, otherwise returns the created node.

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