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

Convert Sorted Array to Balanced BST

📖 Scenario: You have a sorted list of numbers representing data that needs to be organized for fast searching. A balanced Binary Search Tree (BST) is a great way to do this because it keeps the data sorted and allows quick lookups.Imagine you are building a phone book app that needs to quickly find contacts by their phone numbers. You want to convert the sorted list of phone numbers into a balanced BST to make searching efficient.

🎯 Goal: Build a balanced Binary Search Tree (BST) from a given sorted array of numbers. The BST should be balanced, meaning the left and right subtrees of every node differ in height by no more than one.You will write code to create tree nodes, pick the middle element as the root, and recursively build left and right subtrees.

📋 What You'll Learn

Create a TreeNode class with val, left, and right properties

Use a recursive function sortedArrayToBST that takes a sorted array and returns the root of the balanced BST

Pick the middle element of the current array/subarray as the root node

Recursively build left subtree from the left half of the array

Recursively build right subtree from the right half of the array

Print the BST nodes in preorder traversal (root, left, right) to verify the structure

💡 Why This Matters

🌍 Real World

Balanced BSTs are used in databases, file systems, and search engines to organize data for fast searching and insertion.

💼 Career

Understanding how to convert sorted data into balanced trees is important for software engineers working on efficient data storage, retrieval, and algorithms.

1

Create the TreeNode class

Create a class called TreeNode with a constructor that takes a parameter val and sets this.val to it. Also initialize this.left and this.right to null.

DSA Javascript

# Your code here

Hint

Think of each tree node as a box holding a value and two empty slots for left and right child nodes.

2

Set up the sorted array

Create a constant array called nums with these exact values: [1, 2, 3, 4, 5, 6, 7].

DSA Javascript

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

// Create the sorted array nums
// Your code here

Hint

This array is already sorted, which is perfect for building a balanced BST.

3

Write the recursive function to build the BST

Write a function called sortedArrayToBST that takes a parameter arr. Inside, if arr.length is 0, return null. Otherwise, find the middle index as Math.floor(arr.length / 2). Create a TreeNode with the middle element. Recursively assign root.left by calling sortedArrayToBST on the left half of the array, and root.right by calling it on the right half. Return the root node.

DSA Javascript

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

const nums = [1, 2, 3, 4, 5, 6, 7];

// Write the sortedArrayToBST function
// Your code here

Hint

Use the middle element as the root to keep the tree balanced. Use array slicing to get left and right parts.

4

Print the BST nodes in preorder traversal

Write a function called preorderTraversal that takes a node. If node is null, return an empty array. Otherwise, return an array with node.val followed by the result of preorderTraversal(node.left) and then preorderTraversal(node.right). Then, create a variable root by calling sortedArrayToBST(nums). Finally, print the result of preorderTraversal(root) using console.log.

DSA Javascript

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

const nums = [1, 2, 3, 4, 5, 6, 7];

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

// Write preorderTraversal function and print the preorder traversal of the BST
// Your code here

Hint

Preorder traversal visits root first, then left subtree, then right subtree. Use recursion to collect values.

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