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

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

Execution Sample

DSA Javascript

function sortedArrayToBST(arr) {
  if (!arr.length) return null;
  const mid = Math.floor(arr.length / 2);
  const root = { val: arr[mid] };
  root.left = sortedArrayToBST(arr.slice(0, mid));
  root.right = sortedArrayToBST(arr.slice(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	Current Array	Middle Element	Node Created	Left Subtree Call	Right Subtree Call	Visual State
1	Start	[1,2,3,4,5,6,7]	4	Node(4)	[1,2,3]	[5,6,7]	4 / \
2	Left subtree root	[1,2,3]	2	Node(2)	[1]	[3]	4 / \ 2
3	Left subtree left leaf	[1]	1	Node(1)	[]	[]	4 / \ 2 /
4	Left subtree right leaf	[3]	3	Node(3)	[]	[]	4 / \ 2 3 /
5	Right subtree root	[5,6,7]	6	Node(6)	[5]	[7]	4 / \ 2 6 / \ / \
6	Right subtree left leaf	[5]	5	Node(5)	[]	[]	4 / \ 2 6 / \ / \ 1 3 5 7
7	Right subtree right leaf	[7]	7	Node(7)	[]	[]	4 / \ 2 6 / \ / \ 1 3 5 7
8	Return root	N/A	N/A	N/A	N/A	N/A	Balanced BST complete
9	Exit	N/A	N/A	N/A	N/A	N/A	All nodes created, recursion ends

💡 All subarrays processed, recursion ends with balanced BST root returned

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
arr	[1,2,3,4,5,6,7]	[1,2,3,4,5,6,7]	[1,2,3]	[1]	[3]	[5,6,7]	[5]	[7]	N/A
mid	N/A	3	1	0	0	1	0	0	N/A
root.val	N/A	4	2	1	3	6	5	7	4
left subtree	N/A	pending	Node(2)	Node(1)	Node(3)	Complete	Complete	Complete	Complete
right subtree	N/A	pending	pending	pending	pending	Node(6)	Node(5)	Node(7)	Complete

Key Moments - 3 Insights

Why do we pick the middle element as root?

Picking the middle element (see Step 1 in execution_table) 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 (like in Step 3 and Step 4 calls with []), the function returns null, stopping recursion and creating leaf nodes.

How do left and right subtrees connect to the root?

After creating the root node (Step 1), recursive calls build left and right subtrees which are assigned to root.left and root.right respectively, as shown in Steps 2-7.

Visual Quiz - 3 Questions

Look at the execution_table, what is the middle element chosen at Step 5?

A 6

B 5

C 7

D 4

💡 Hint

Check the 'Middle Element' column at Step 5 in execution_table.

At which step does the recursion create the left leaf node with value 1?

A Step 2

B Step 3

C Step 4

D Step 6

💡 Hint

Look at the 'Node Created' column and 'Current Array' at Step 3.

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

A A node with value 0

B An error

C null

D An empty array

💡 Hint

Refer to the base case in the code sample where empty array returns null.

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 array returns null
- Result is height-balanced BST

Full Transcript

This concept converts a sorted array into a balanced binary search tree by choosing the middle element as the root node. The array is split into left and right halves recursively, building left and right subtrees. When the subarray is empty, recursion stops returning null, creating leaf nodes. This ensures the tree is balanced with minimal height. The code uses recursion and array slicing to build the tree step-by-step.

Practice

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

easy

A. To create a linked list from the array

B. To reverse the array elements

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

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 for faster search operations.

2. Step 2: Recognize the importance of balance

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

3. Final Answer:

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

4. Quick Check:

   Balanced BST = minimal height = efficient search [OK]

Hint: Pick the option about balanced tree and efficient search [OK]

Common Mistakes:

• Thinking the goal is to reverse or sort the array again
• Confusing BST with linked list
• Ignoring the balance aspect of the tree

2. Which of the following is the correct way to find the middle index of an array arr in JavaScript for building a balanced BST?

easy

A. const mid = Math.floor(arr.length / 2);

B. const mid = arr.length / 2;

C. const mid = Math.ceil(arr.length / 2);

D. const mid = arr.length - 1;

Solution

1. Step 1: Understand array indexing

   Array indices start at 0, so to get the middle index, we divide length by 2 and take the floor to get an integer index.

2. Step 2: Use Math.floor for integer index

   Using Math.floor(arr.length / 2) gives the correct middle index for both even and odd lengths.

3. Final Answer:

   const mid = Math.floor(arr.length / 2); -> Option A

4. Quick Check:

   Middle index = floor(length/2) [OK]

Hint: Use Math.floor to get integer middle index [OK]

Common Mistakes:

• Using division without floor, resulting in float index
• Using Math.ceil which may pick wrong middle
• Using last index instead of middle

3. What will be the root node value of the balanced BST created from the sorted array [1, 3, 5, 7, 9]?

medium

A. 3

B. 5

C. 7

D. 9

Solution

1. Step 1: Find the middle element of the array

   The array length is 5, middle index = floor(5/2) = 2, so middle element is arr[2] = 5.

2. Step 2: Middle element becomes root

   In balanced BST from sorted array, the middle element is chosen as root to keep tree balanced.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Middle element = root = 5 [OK]

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

Common Mistakes:

• Picking first or last element as root
• Using ceil instead of floor for middle index
• Confusing array index with value

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

function sortedArrayToBST(arr) {
  if (!arr.length) return null;
  const mid = Math.floor(arr.length / 2);
  const root = { val: arr[mid], left: null, right: null };
  root.left = sortedArrayToBST(arr.slice(0, mid));
  root.right = sortedArrayToBST(arr.slice(mid));
  return root;
}

What is the bug in this code?

medium

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

B. The base case should check for arr === null instead of length

C. The mid index calculation is incorrect

D. The root node is not created properly

Solution

1. Step 1: Analyze the slicing for right subtree

   The right subtree should exclude the middle element already used as root, so slice should start from mid + 1.

2. Step 2: Identify the bug

   Using arr.slice(mid) includes the middle element again in the right subtree, causing duplicate nodes and incorrect tree.

3. Final Answer:

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

4. Quick Check:

   Right subtree slice = arr.slice(mid + 1) [OK]

Hint: Right subtree excludes middle element: slice from mid+1 [OK]

Common Mistakes:

• Including middle element in both subtrees
• Wrong base case condition
• Incorrect mid calculation

5. Given the sorted array [-10, -3, 0, 5, 9], what is the preorder traversal (root-left-right) of the balanced BST created by the standard algorithm?

hard

A. [0, -10, -3, 5, 9]

B. [-3, -10, 0, 5, 9]

C. [5, 0, -10, -3, 9]

D. [0, -3, -10, 9, 5]

Solution

1. Step 1: Build the balanced BST

   Middle index = Math.floor(5/2) = 2, root = 0. Left subarray [-10, -3], length=2, mid=Math.floor(2/2)=1, left child = -3 (left of -3: [-10] mid=0 value -10; right of -3: empty). Right subarray [5, 9], length=2, mid=1, right child = 9 (left of 9: [5]; right of 9: empty).

2. Step 2: Perform preorder traversal (root-left-right)

   0, then left subtree: -3 then -10, then right subtree: 9 then 5. Result: [0, -3, -10, 9, 5].

3. Final Answer:

   [0, -3, -10, 9, 5] -> Option D

4. Quick Check:

   Preorder = root-left-right = [0, -3, -10, 9, 5] [OK]

Hint: Preorder = root, then left subtree, then right subtree [OK]

Common Mistakes:

• Wrong middle element selection for subtrees
• Confusing preorder with inorder or postorder
• Incorrect subtree construction