Convert Sorted Array to Balanced BST in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Balanced BST Inorder Traversal

Given the following JavaScript code that converts a sorted array to a balanced BST and then prints its inorder traversal, what is the output?

DSA Javascript

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

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

function inorderTraversal(root) {
  if (!root) return [];
  return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)];
}

const nums = [1, 2, 3, 4, 5, 6, 7];
const bstRoot = sortedArrayToBST(nums);
console.log(inorderTraversal(bstRoot).join(' -> ') + ' -> null');

A 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null

B 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7 -> null

C 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

D null

💡 Hint

Inorder traversal of a BST returns the nodes in sorted order.

The function builds a balanced BST by choosing the middle element as root recursively. Inorder traversal of a BST always returns the sorted array. So the output matches the original sorted array.

🧠 Conceptual

intermediate

Height of Balanced BST from Sorted Array

If you convert a sorted array of length 15 into a balanced BST using the middle element as root recursively, what will be the height of the resulting BST?

A 4

B 3

C 5

D 15

💡 Hint

Height of balanced BST is about log2(n+1).

A balanced BST built from a sorted array has height approximately log base 2 of (n+1). For n=15, log2(16) = 4.

🔧 Debug

advanced

Identify the Bug in BST Construction

What is the output of this code snippet? Identify if there is a bug and what it causes.

DSA Javascript

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

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

function preorderTraversal(root) {
  if (!root) return [];
  return [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)];
}

const nums = [1, 2, 3, 4, 5];
const bstRoot = sortedArrayToBST(nums);
console.log(preorderTraversal(bstRoot).join(' -> ') + ' -> null');

A 3 -> 1 -> 2 -> 5 -> 4 -> null

B 4 -> 2 -> 1 -> 3 -> 5 -> null (with off-by-one bug)

C 4 -> 2 -> 1 -> 3 -> 5 -> null

D TypeError due to invalid slice indices

💡 Hint

Check how mid index is calculated and how slice works.

Using Math.ceil for mid causes the root to be chosen incorrectly, leading to an unbalanced tree and incorrect preorder traversal output.

🚀 Application

advanced

Number of Nodes in Balanced BST

If you build a balanced BST from a sorted array of length 31, how many nodes will the left subtree of the root have?

A 30

B 16

C 15

D 31

💡 Hint

The root is the middle element, left subtree has elements before it.

For 31 elements, middle index is 15 (0-based), so left subtree has 15 nodes (indices 0 to 14).

❓ Predict Output

expert

Output of Level Order Traversal of Balanced BST

What is the output of the level order traversal of the balanced BST created from the sorted array [10, 20, 30, 40, 50, 60, 70]?

DSA Javascript

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

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

function levelOrderTraversal(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

const nums = [10, 20, 30, 40, 50, 60, 70];
const bstRoot = sortedArrayToBST(nums);
console.log(levelOrderTraversal(bstRoot).join(' -> ') + ' -> null');

A 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> null

B null

C 70 -> 60 -> 50 -> 40 -> 30 -> 20 -> 10 -> null

D 40 -> 20 -> 60 -> 10 -> 30 -> 50 -> 70 -> null

💡 Hint

Level order visits nodes level by level from root.

The middle element 40 is root, left subtree root 20, right subtree root 60. Level order visits 40, then 20 and 60, then their children.