Convert Sorted Array to Balanced BST in DSA Go - 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 Go

func sortedArrayToBST(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  mid := len(nums) / 2
  root := &TreeNode{Val: nums[mid]}
  root.Left = sortedArrayToBST(nums[:mid])
  root.Right = sortedArrayToBST(nums[mid+1:])
  return root
}

This function 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]	nil	nil	Empty tree
2	Find middle	[1, 2, 3, 4, 5, 6, 7]	Node(4)	root = Node(4)	4
3	Build left subtree	[1, 2, 3]	Node(2)	root.Left = Node(2)	4 / 2
4	Build left subtree of left	[1]	Node(1)	Node(2).Left = Node(1)	4 / 2 / 1
5	Build right subtree of left	[3]	Node(3)	Node(2).Right = Node(3)	4 / 2 / \ 1 3
6	Build right subtree	[5, 6, 7]	Node(6)	root.Right = Node(6)	4 / \ 2 6 / \
7	Build left subtree of right	[5]	Node(5)	Node(6).Left = Node(5)	4 / \ 2 6 / \ / 1 3 5
8	Build right subtree of right	[7]	Node(7)	Node(6).Right = Node(7)	4 / \ 2 6 / \ / \ 1 3 5 7
9	Return root	Full tree	nil	nil	Balanced BST complete
10	End	No more subarrays	nil	nil	Construction finished

💡 All subarrays processed, recursion ends, balanced BST constructed

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	Final
nums	[1,2,3,4,5,6,7]	[1,2,3,4,5,6,7]	[1,2,3]	[5,6,7]	N/A
mid	N/A	3	1	1	N/A
root	nil	Node(4)	Node(4)	Node(4)	Node(4)
root.Left	nil	nil	Node(2)	Node(2)	Node(2)
root.Right	nil	nil	nil	Node(6)	Node(6)

Key Moments - 3 Insights

Why do we pick the middle element as root?

Choosing the middle element (see Step 2 in execution_table) ensures the tree stays balanced because it divides the array into two equal halves for left and right subtrees.

What happens when the subarray is empty?

When the subarray is empty (like after Step 9), the function returns nil, which means no node is created, stopping recursion on that branch.

How do left and right pointers get assigned?

After creating the root node, recursive calls build left and right subtrees (Steps 3-8), and their returned nodes are assigned to root.Left and root.Right respectively.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, which node is created and where is it attached?

A Node(1) attached as left child of Node(2)

B Node(3) attached as right child of Node(4)

C Node(5) attached as left child of Node(6)

D Node(7) attached as right child of Node(6)

💡 Hint

Check Step 4 in execution_table under 'Node Created' and 'Pointer Changes'

At which step does the right subtree of the root start building?

A Step 3

B Step 6

C Step 8

D Step 2

💡 Hint

Look at the 'Operation' column in execution_table for building right subtree

If the input array was empty, what would the function return?

A An error

B A node with value 0

C nil (no node)

D A node with value from the first element

💡 Hint

Refer to Step 1 and the base case in the code sample where len(nums) == 0

Concept Snapshot

Convert Sorted Array to Balanced BST:
- Pick middle element as root
- Recursively build left subtree from left half
- Recursively build right subtree from right half
- Base case: empty subarray returns nil
- Result is a height-balanced BST

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 array is split into left and right halves, which become the left and right subtrees respectively. The recursion stops when the subarray is empty, returning nil. This approach ensures the tree is balanced because each root divides the array evenly. The execution table shows each step of node creation and pointer assignment, building the tree from bottom up. Key moments clarify why the middle element is chosen and how recursion stops. The visual quiz tests understanding of node placement and recursion steps.

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 for efficient search

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 build a BST that is balanced, meaning the tree height is minimized to allow fast searching.

2. Step 2: Why minimal height matters

   A balanced BST ensures operations like search, insert, and delete run in O(log n) time, which is efficient.

3. Final Answer:

   To create a BST with minimal height for efficient search -> Option A

4. Quick Check:

   Balanced BST = minimal height = efficient search [OK]

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

Common Mistakes:

• Confusing BST with linked list
• Thinking sorting again is needed
• Ignoring tree balance importance

2. Which Go function signature correctly represents the recursive function to convert a sorted array to a balanced BST?

easy

A. func sortedArrayToBST(nums []int) *TreeNode

B. func sortedArrayToBST(nums int) TreeNode

C. func sortedArrayToBST(nums []int) int

D. func sortedArrayToBST(nums []int) []int

Solution

1. Step 1: Identify input and output types

   The function takes a slice of integers (sorted array) and returns a pointer to the root TreeNode of the BST.

2. Step 2: Match correct Go syntax

   func sortedArrayToBST(nums []int) *TreeNode matches: input is []int, output is *TreeNode pointer, which is standard for tree nodes in Go.

3. Final Answer:

   func sortedArrayToBST(nums []int) *TreeNode -> Option A

4. Quick Check:

   Input []int, output *TreeNode pointer [OK]

Hint: Look for slice input and pointer to TreeNode output [OK]

Common Mistakes:

• Using int instead of slice for input
• Returning int or slice instead of TreeNode pointer
• Missing pointer in return type

3. Given the sorted array [1, 2, 3, 4, 5], what is the root value of the balanced BST created by the standard algorithm?

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Find middle element of array

   The middle index of [1, 2, 3, 4, 5] is 2 (0-based), so middle element is 3.

2. Step 2: Root is middle element

   The root of the balanced BST is the middle element to balance left and right subtrees.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Middle element = root = 3 [OK]

Hint: Root is middle element of sorted array [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one error in middle index
• Confusing index with value

4. Consider this Go code snippet to convert a sorted array to a balanced BST:

func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    mid := len(nums) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = sortedArrayToBST(nums[:mid])
    root.Right = sortedArrayToBST(nums[mid:])
    return root
}

What is the bug in this code?

medium

A. The function should return an int, not *TreeNode

B. The base case should check for len(nums) < 0

C. The root node is created with wrong value

D. The right subtree slice should start from mid+1, not mid

Solution

1. Step 1: Analyze slicing for right subtree

   The right subtree slice uses nums[mid:], which includes the middle element again, causing duplicate nodes.

2. Step 2: Correct slice to exclude middle element

   Right subtree should start from mid+1 to avoid including root again.

3. Final Answer:

   The right subtree slice should start from mid+1, not mid -> Option D

4. Quick Check:

   Right slice = nums[mid+1:] to avoid duplicates [OK]

Hint: Right slice must exclude middle element by starting at mid+1 [OK]

Common Mistakes:

• Using mid instead of mid+1 for right slice
• Wrong base case condition
• Returning wrong type

5. You have a sorted array [10, 20, 30, 40, 50, 60, 70]. After converting it to a balanced BST, what is the inorder traversal of the BST?

hard

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

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

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

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

Solution

1. Step 1: Understand inorder traversal of BST

   Inorder traversal visits nodes in ascending order for BST, so it returns the sorted array.

2. Step 2: Confirm traversal matches original array

   Since the BST is built from sorted array, inorder traversal outputs the same sorted sequence.

3. Final Answer:

   [10, 20, 30, 40, 50, 60, 70] -> 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
• Assuming traversal changes order
• Mixing up traversal outputs