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

↓

Balanced BST constructed

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

Execution Sample

DSA Java

int mid = (start + end) / 2;
TreeNode root = new TreeNode(arr[mid]);
root.left = buildBST(arr, start, mid - 1);
root.right = buildBST(arr, mid + 1, end);
return root;

This code picks the middle element as root and recursively builds left and right subtrees from subarrays.

Execution Table

Step	Operation	Subarray Range	Node Created	Pointer Changes	Visual State
1	Find middle of [0..6]	[0..6]	Node(4)	root -> Node(4)	4
2	Build left subtree of Node(4)	[0..2]	Node(2)	root.left -> Node(2)	4 / 2
3	Build left subtree of Node(2)	[0..0]	Node(1)	Node(2).left -> Node(1)	4 / 2 / 1
4	Build left subtree of Node(1)	[0..-1]	null	Node(1).left -> null	No change
5	Build right subtree of Node(1)	[1..0]	null	Node(1).right -> null	No change
6	Build right subtree of Node(2)	[2..2]	Node(3)	Node(2).right -> Node(3)	4 / 2 / \ 1 3
7	Build left subtree of Node(3)	[2..1]	null	Node(3).left -> null	No change
8	Build right subtree of Node(3)	[3..2]	null	Node(3).right -> null	No change
9	Build right subtree of Node(4)	[4..6]	Node(6)	root.right -> Node(6)	4 / \ 2 6 / \
10	Build left subtree of Node(6)	[4..4]	Node(5)	Node(6).left -> Node(5)	4 / \ 2 6 / \ / 1 3 5
11	Build left subtree of Node(5)	[4..3]	null	Node(5).left -> null	No change
12	Build right subtree of Node(5)	[5..4]	null	Node(5).right -> null	No change
13	Build right subtree of Node(6)	[6..6]	Node(7)	Node(6).right -> Node(7)	4 / \ 2 6 / \ / \ 1 3 5 7
14	Build left subtree of Node(7)	[6..5]	null	Node(7).left -> null	No change
15	Build right subtree of Node(7)	[7..6]	null	Node(7).right -> null	No change
16	Return root Node(4)	Full tree built	N/A	N/A	Balanced BST complete

💡 All subarrays processed; recursion ends when start > end (null nodes).

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 9	Final
start	0	0	0	4	N/A
end	6	6	2	6	N/A
mid	N/A	3	1	5	N/A
root	null	Node(4)	Node(4)	Node(4)	Node(4)
current node	null	Node(4)	Node(2)	Node(6)	N/A

Key Moments - 3 Insights

Why do we pick the middle element as root instead of the first or last?

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

What happens when the subarray range is invalid (start > end)?

When start > end (e.g., Step 4), we return null, meaning no node is created, which stops recursion on that branch.

How do left and right pointers get assigned during recursion?

At each step (e.g., Steps 2 and 9), after creating a node, recursive calls assign left and right children by building subtrees from left and right subarrays.

Visual Quiz - 3 Questions

Look at the execution_table at Step 6, which node is created and attached?

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

B Node(3) as right child of Node(2)

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

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

💡 Hint

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

At which step does the recursion return null for the left subtree of Node(1)?

A Step 4

B Step 5

C Step 7

D Step 11

💡 Hint

Look for subarray ranges where start > end and Node Created is null

If the input array length was 3 instead of 7, how would the root node change?

A Root would be the last element

B Root would be the first element

C Root would be the middle element of the smaller array

D No root node would be created

💡 Hint

Recall the concept_flow and how the middle element is always chosen as root

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: return null if subarray empty
- Result: height-balanced BST

Full Transcript

To convert a sorted array into a balanced binary search tree, we pick the middle element as the root node. Then, we recursively do the same for the left half of the array to build the left subtree and for the right half to build the right subtree. When the subarray is empty, we return null, ending recursion. This approach ensures the tree is balanced because each node divides the array into two roughly equal parts. The execution table shows each step of node creation and pointer assignment, building the tree from bottom up until the full balanced BST is constructed.

Practice

1. What is the main goal when converting a sorted array to a balanced Binary Search Tree (BST)?

easy

A. To reverse the array elements

B. To create a linked list from the array

C. To sort the array again

D. To create a BST with minimal height for efficient search

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.

2. Step 2: Reason about balanced BST benefits

   A balanced BST ensures search operations are efficient, typically O(log n) time, by minimizing height.

3. Final Answer:

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

4. Quick Check:

   Balanced BST = minimal height = efficient search [OK]

Hint: Balanced BST means minimal height for fast search [OK]

Common Mistakes:

• Thinking the array needs to be reversed
• Confusing BST with linked list
• Ignoring the balance requirement

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

easy

A. public TreeNode sortedArrayToBST(int[] nums, int left, int right)

B. public void sortedArrayToBST(int[] nums)

C. public int sortedArrayToBST(int[] nums, int start)

D. public TreeNode sortedArrayToBST(int[] nums, int mid)

Solution

1. Step 1: Identify parameters needed for recursion

   The recursive function needs the array and two indices (left and right) to define the current subarray.

2. Step 2: Check return type and parameters

   The function returns a TreeNode (root of subtree) and takes int[] nums, int left, int right as parameters.

3. Final Answer:

   public TreeNode sortedArrayToBST(int[] nums, int left, int right) -> Option A

4. Quick Check:

   Recursive BST function needs array + left + right indices [OK]

Hint: Recursive BST needs array and left-right indices [OK]

Common Mistakes:

• Missing left and right indices parameters
• Wrong return type (void or int)
• Using mid as parameter instead of indices

3. What is the output tree structure (inorder traversal) after running the code below?

int[] nums = {1, 2, 3, 4, 5};
TreeNode root = sortedArrayToBST(nums, 0, nums.length - 1);
printInorder(root);

Assuming printInorder prints nodes in inorder.

medium

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

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

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

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

Solution

1. Step 1: Understand inorder traversal of BST

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

2. Step 2: Check input array and output

   The input array is sorted: [1, 2, 3, 4, 5]. The inorder traversal of the BST built from it will be the same sorted array.

3. Final Answer:

   [1, 2, 3, 4, 5] -> Option A

4. Quick Check:

   Inorder traversal of BST = sorted array [OK]

Hint: Inorder traversal of BST returns sorted array [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Expecting reversed or shuffled output
• Not understanding BST property

4. Identify the error in the following code snippet for converting a sorted array to a balanced BST:

public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
  if (left > right) return null;
  int mid = (left + right) / 2;
  TreeNode root = new TreeNode(nums[mid]);
  root.left = sortedArrayToBST(nums, left, mid - 1);
  root.right = sortedArrayToBST(nums, mid + 1, right);
  return root;
}

// Called with sortedArrayToBST(nums, 0, nums.length);

medium

A. The base case condition is incorrect

B. The initial call uses wrong right index

C. The mid calculation causes overflow

D. The TreeNode constructor is missing

Solution

1. Step 1: Check the initial call parameters

   The function expects right to be the last valid index, but the call uses nums.length which is out of bounds.

2. Step 2: Understand array indexing

   Array indices go from 0 to nums.length - 1, so right should be nums.length - 1.

3. Final Answer:

   The initial call uses wrong right index -> Option B

4. Quick Check:

   Right index must be nums.length - 1, not nums.length [OK]

Hint: Right index = last array index (length - 1) [OK]

Common Mistakes:

• Passing nums.length as right index
• Ignoring zero-based indexing
• Assuming mid calculation causes overflow here

5. Given a sorted array with duplicate values: int[] nums = {1, 2, 2, 3, 4, 4, 5}; Which statement about the balanced BST created by sortedArrayToBST(nums, 0, nums.length - 1) is true?

hard

A. The BST will only keep unique values in left subtree

B. The BST will remove duplicates automatically

C. The BST will contain duplicate nodes for repeated values

D. The BST will throw an error due to duplicates

Solution

1. Step 1: Understand BST property with duplicates

   BST can contain duplicates; they are usually placed consistently either left or right subtree.

2. Step 2: Check behavior of conversion from sorted array

   The conversion uses array elements as nodes directly, so duplicates appear as separate nodes in the tree.

3. Final Answer:

   The BST will contain duplicate nodes for repeated values -> Option C

4. Quick Check:

   Duplicates in array = duplicates in BST nodes [OK]

Hint: Duplicates in array become duplicate nodes in BST [OK]

Common Mistakes:

• Assuming duplicates are removed automatically
• Thinking duplicates cause errors
• Believing duplicates go only to left subtree