Convert Sorted Array to Balanced BST in DSA Java - Build from Scratch

Convert Sorted Array to Balanced BST

📖 Scenario: You have a sorted list of numbers representing sorted data. You want to organize this data into a balanced tree structure so that searching for any number is fast and efficient.

🎯 Goal: Build a balanced binary search tree (BST) from a sorted array of integers. The tree should be balanced, meaning the left and right subtrees of any node differ in height by at most one.

📋 What You'll Learn

Create an integer array called sortedArray with the exact values: {1, 2, 3, 4, 5, 6, 7}

Create a class TreeNode with integer val, and left and right child nodes

Write a method sortedArrayToBST that takes the array and returns the root of the balanced BST

Print the tree nodes in in-order traversal to verify the tree structure

💡 Why This Matters

🌍 Real World

Balanced binary search trees are used in databases and file systems to keep data sorted and allow fast search, insert, and delete operations.

💼 Career

Understanding how to convert sorted data into balanced trees is important for software engineers working on search engines, databases, and performance-critical applications.

1

Create the sorted array

Create an integer array called sortedArray with the exact values {1, 2, 3, 4, 5, 6, 7}.

DSA Java

// Create the sorted array
// Your code here

Hint

Use int[] sortedArray = {1, 2, 3, 4, 5, 6, 7}; to create the array.

2

Define the TreeNode class

Define a class called TreeNode with an integer variable val, and two TreeNode variables called left and right.

DSA Java

int[] sortedArray = {1, 2, 3, 4, 5, 6, 7};
// Define the TreeNode class below
// Your code here

Hint

Define the class with the constructor that sets val and initializes left and right to null.

3

Write the method to convert sorted array to balanced BST

Write a method called sortedArrayToBST that takes an integer array nums and returns a TreeNode representing the root of a balanced BST. Use a helper method buildBST with parameters nums, start, and end to build the tree recursively.

DSA Java

int[] sortedArray = {1, 2, 3, 4, 5, 6, 7};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// Write sortedArrayToBST and buildBST methods below
// Your code here

Hint

Use the middle element as root, recursively build left and right subtrees from subarrays.

4

Print the tree in in-order traversal

Write a method called inOrderTraversal that takes a TreeNode root and prints the node values in in-order (left, root, right). Then call inOrderTraversal on the BST created from sortedArray.

DSA Java

int[] sortedArray = {1, 2, 3, 4, 5, 6, 7};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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

    private TreeNode buildBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = buildBST(nums, start, mid - 1);
        node.right = buildBST(nums, mid + 1, end);
        return node;
    }
}

// Write inOrderTraversal method and print the traversal of the BST
// Your code here

Hint

Use recursion to print left subtree, then root value, then right subtree. Call this method on the BST root.

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