Convert Sorted Array to Balanced BST in DSA Java

Mental Model

We pick the middle element of the sorted array as the root to keep the tree balanced. Then we do the same for left and right halves to build subtrees.

Analogy: Imagine dividing a sorted list of books evenly to put the middle book on a shelf center, then placing the left half on the left shelf and right half on the right shelf, repeating this to keep shelves balanced.

Sorted array: [1, 2, 3, 4, 5, 6, 7]
Balanced BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

Dry Run Walkthrough

Input: sorted array: [1, 2, 3, 4, 5, 6, 7]

Goal: Build a balanced binary search tree from the sorted array

Step 1: Pick middle element 4 as root

4
Left array: [1, 2, 3]
Right array: [5, 6, 7]

Why: Middle element keeps tree balanced by splitting array evenly

Step 2: Build left subtree from [1, 2, 3], pick 2 as root

    4
   / 
  2
Left array: [1]
Right array: [3]

Why: Recursively pick middle to keep left subtree balanced

Step 3: Build left child of 2 from [1], pick 1 as leaf

    4
   / 
  2
 / 
1

Why: Single element becomes leaf node

Step 4: Build right child of 2 from [3], pick 3 as leaf

    4
   / 
  2
 / \
1   3

Why: Single element becomes leaf node

Step 5: Build right subtree from [5, 6, 7], pick 6 as root

    4
   / \
  2   6
 / \ 
1   3
Right array left: [5]
Right array right: [7]

Why: Recursively pick middle to keep right subtree balanced

Step 6: Build left child of 6 from [5], pick 5 as leaf

    4
   / \
  2   6
 / \ / 
1  3 5

Why: Single element becomes leaf node

Step 7: Build right child of 6 from [7], pick 7 as leaf

    4
   / \
  2   6
 / \ / \
1  3 5  7

Why: Single element becomes leaf node

Result:

Balanced BST:
      4
     / \
    2   6
   / \ / \
  1  3 5  7

Annotated Code

DSA Java

public class ConvertSortedArrayToBST {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }

    private static TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) return null; // base case: no elements

        int mid = left + (right - left) / 2; // pick middle element
        TreeNode root = new TreeNode(nums[mid]); // create root node

        root.left = buildBST(nums, left, mid - 1); // build left subtree
        root.right = buildBST(nums, mid + 1, right); // build right subtree

        return root; // return root of this subtree
    }

    public static void printInOrder(TreeNode root) {
        if (root == null) return;
        printInOrder(root.left);
        System.out.print(root.val + " ");
        printInOrder(root.right);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        TreeNode root = sortedArrayToBST(nums);
        printInOrder(root);
        System.out.println();
    }
}

if (left > right) return null; // base case: no elements

stop recursion when no elements left to process

int mid = left + (right - left) / 2; // pick middle element

choose middle index to keep tree balanced

TreeNode root = new TreeNode(nums[mid]); // create root node

create node with middle element as root

root.left = buildBST(nums, left, mid - 1); // build left subtree

recursively build left subtree from left half

root.right = buildBST(nums, mid + 1, right); // build right subtree

recursively build right subtree from right half

return root; // return root of this subtree

return constructed subtree root to caller

Output

1 2 3 4 5 6 7 

Complexity Analysis

Time: O(n) because each element is visited once to create a node

Space: O(log n) due to recursion stack depth for balanced tree

vs Alternative: Compared to inserting elements one by one into BST (O(n log n)), this method builds balanced BST in linear time

Edge Cases

empty array

returns null tree (no nodes)

DSA Java

if (left > right) return null; // base case: no elements

array with one element

creates single node tree

DSA Java

if (left > right) return null; // base case: no elements

array with two elements

root is middle (first element), right child is second element

DSA Java

int mid = left + (right - left) / 2; // pick middle element

When to Use This Pattern

When you see a sorted array and need a balanced BST, use the middle element as root and recursively build subtrees from halves to ensure balance.

Common Mistakes

Mistake: Picking first or last element as root instead of middle, causing unbalanced tree
Fix: Always pick middle element using mid = left + (right - left) / 2

Mistake: Not handling base case when left > right, causing infinite recursion
Fix: Add base case: if (left > right) return null

Summary

Builds a balanced binary search tree from a sorted array by recursively choosing middle elements as roots.

Use when you need a balanced BST from sorted data for efficient search and traversal.

The key is picking the middle element to keep left and right subtrees balanced.

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