Convert Sorted Array to Balanced BST in DSA Python - Execution Trace

Concept Flow - Convert Sorted Array to Balanced BST

Start with sorted array

↓

Find middle element

→Create root node with middle

↓

Left subarray

→Recursively build left subtree

↓

Right subarray

→Recursively build right subtree

↓

Attach left and right subtrees to root

↓

Return root node of balanced BST

Split the sorted array by middle element to create root, then recursively build left and right subtrees from subarrays.

Execution Sample

DSA Python

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

This code converts a sorted array into a balanced binary search tree by recursively choosing the middle element as root.

Execution Table

Step	Operation	Subarray	Node Created	Pointer Changes	Visual State
1	Start with full array	[1, 2, 3, 4, 5, 6, 7]	None	None	Empty tree
2	Find middle	[1, 2, 3, 4, 5, 6, 7]	4	root = 4	4
3	Build left subtree	[1, 2, 3]	None	root.left pending	4 -> left subtree pending
4	Find middle	[1, 2, 3]	2	root.left = 2	4 / 2
5	Build left subtree	[1]	None	2.left pending	4 / 2 -> left subtree pending
6	Find middle	[1]	1	2.left = 1	4 / 2 / 1
7	Build left subtree	[]	None	1.left = None	4 / 2 / 1 (leaf)
8	Build right subtree	[]	None	1.right = None	4 / 2 / 1 (leaf)
9	Build right subtree	[3]	None	2.right pending	4 / 2 / \ 1 right subtree pending
10	Find middle	[3]	3	2.right = 3	4 / 2 / \ 1 3
11	Build left subtree	[]	None	3.left = None	4 / 2 / \ 1 3 (leaf)
12	Build right subtree	[]	None	3.right = None	4 / 2 / \ 1 3 (leaf)
13	Build right subtree	[5, 6, 7]	None	root.right pending	4 / \ 2 right subtree pending
14	Find middle	[5, 6, 7]	6	root.right = 6	4 / \ 2 6
15	Build left subtree	[5]	None	6.left pending	4 / \ 2 6 /
16	Find middle	[5]	5	6.left = 5	4 / \ 2 6 / 5
17	Build left subtree	[]	None	5.left = None	4 / \ 2 6 / 5 (leaf)
18	Build right subtree	[]	None	5.right = None	4 / \ 2 6 / 5 (leaf)
19	Build right subtree	[7]	None	6.right pending	4 / \ 2 6 / \ 5 right subtree pending
20	Find middle	[7]	7	6.right = 7	4 / \ 2 6 / \ 5 7
21	Build left subtree	[]	None	7.left = None	4 / \ 2 6 / \ 5 7 (leaf)
22	Build right subtree	[]	None	7.right = None	4 / \ 2 6 / \ 5 7 (leaf)
23	Return root	Full tree built	None	None	Balanced BST complete

💡 All subarrays empty, recursion ends, full balanced BST constructed

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 10	After Step 14	Final
arr	[1,2,3,4,5,6,7]	[1,2,3,4,5,6,7]	[1,2,3]	[1]	[3]	[5,6,7]	[1,2,3,4,5,6,7]
mid	None	3	1	0	0	1	None
root	None	4	2	1	3	6	4
root.left	None	None	2	2	2	2	2
root.right	None	None	None	None	None	6	6

Key Moments - 3 Insights

Why do we pick the middle element as root?

Choosing the middle element (see Step 2, 4, 6, 10, 14) ensures the tree stays balanced by evenly splitting the array into left and right subtrees.

What happens when the subarray is empty?

When the subarray is empty (see Steps 7, 8, 11, 12, 17, 18, 21, 22), the function returns None, marking a leaf node's child, stopping recursion.

How do left and right pointers get assigned?

After creating a node, recursive calls assign left and right children (see Steps 4, 6, 10, 14, 16, 20). The pointers root.left and root.right are updated accordingly.

Visual Quiz - 3 Questions

Look at the execution table, what node is created at Step 14?

A Node with value 6

B Node with value 5

C Node with value 7

D Node with value 4

💡 Hint

Check the 'Node Created' column at Step 14 in the execution_table

At which step does the recursion return None for the left subtree of node 1?

A Step 11

B Step 8

C Step 7

D Step 17

💡 Hint

Look for empty subarray returns under node 1 in execution_table Steps 7 and 8

If the input array was [1,2,3], what would be the root node value?

A 1

B 2

C 3

D None

💡 Hint

Recall the middle element is chosen as root; see variable_tracker for mid calculation

Concept Snapshot

Convert Sorted Array to Balanced BST:
- Pick middle element as root
- Recursively build left subtree from left subarray
- Recursively build right subtree from right subarray
- Base case: empty subarray returns None
- Ensures balanced BST with O(log n) height

Full Transcript

This concept converts a sorted array into a balanced binary search tree by recursively selecting the middle element as the root node. The process splits the array into left and right subarrays, building left and right subtrees respectively. When the subarray is empty, recursion stops by returning None, marking leaf nodes. This approach ensures the tree remains balanced, with roughly equal nodes on each side, resulting in efficient search operations. The execution table traces each step, showing node creation, pointer assignments, and the evolving tree structure. Variable tracking shows how the array, middle index, and root pointers change during recursion. Key moments clarify why the middle element is chosen, how empty subarrays end recursion, and how pointers are assigned. Visual quizzes test understanding of node creation steps, recursion base cases, and root selection for smaller arrays.

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