Solving Convert Sorted Array to BST in JavaScript: Step-by-Step Guide

Introduction to Convert Sorted Array to BST

The "Convert Sorted Array to Binary Search Tree" problem is a classic algorithmic challenge that frequently appears in coding interviews and competitive programming. The task is deceptively simple: given an array of integers sorted in ascending order, construct a height-balanced binary search tree (BST). Despite its apparent simplicity, this problem tests your understanding of binary trees, recursion, and the divide-and-conquer paradigm.

In this tutorial, we will walk through the problem step by step, understand the underlying concepts, implement the solution in JavaScript, and discuss best practices and edge cases. By the end, you will have a solid grasp of how to transform a sorted array into a balanced BST efficiently.

What Is a Binary Search Tree?

A Binary Search Tree (BST) is a tree data structure where each node has at most two children, referred to as the left and right child. The BST property dictates that for every node:

All values in the left subtree are less than the node's value.
All values in the right subtree are greater than the node's value.
Both the left and right subtrees must also be BSTs.

This property makes BSTs extremely useful for operations like search, insert, and delete, all of which can be performed in O(log n) time when the tree is balanced. A height-balanced BST is one where the depth of the two subtrees of every node never differs by more than one.

Why Balance Matters

If you insert sorted elements into a BST sequentially, you end up with a degenerate tree that resembles a linked list. This defeats the purpose of using a BST, as operations degrade to O(n) time complexity. Converting a sorted array into a balanced BST ensures optimal performance for subsequent operations.

Why This Problem Matters

This problem is important for several reasons. First, it demonstrates the power of the divide-and-conquer approach, a fundamental algorithm design technique. Second, it reinforces your understanding of tree construction and recursion. Third, balanced BSTs are widely used in real-world applications such as database indexing, in-memory sorted data structures, and implementing associative arrays.

From an interview perspective, this problem allows interviewers to assess multiple skills at once: your ability to reason about tree structures, your comfort with recursion, and your attention to edge cases such as empty arrays or arrays with duplicate values.

Understanding the Approach

The key insight is that the middle element of the sorted array should be the root of the BST. Why? Because all elements to the left of the middle are smaller, and all elements to the right are larger. This naturally satisfies the BST property. By recursively applying the same logic to the left and right halves of the array, we construct a balanced tree.

Step-by-Step Algorithm

Identify the middle element of the current subarray.
Create a new tree node with this middle element as the value.
Recursively build the left subtree using the left half of the array.
Recursively build the right subtree using the right half of the array.
Return the root node.

The base case occurs when the subarray is empty, meaning the left index exceeds the right index. In that case, we return null, indicating no child node exists.

Implementing the Solution in JavaScript

Let us first define the TreeNode class, which represents each node in our BST. Then we will implement the conversion function using recursion.

// Definition for a binary tree node.
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

/**
 * Converts a sorted array to a height-balanced BST.
 * @param {number[]} nums - Sorted array of integers
 * @return {TreeNode} - Root of the balanced BST
 */
function sortedArrayToBST(nums) {
  if (!nums || nums.length === 0) {
    return null;
  }

  return buildTree(nums, 0, nums.length - 1);
}

/**
 * Helper function that recursively builds the BST.
 * @param {number[]} nums - The sorted array
 * @param {number} left - Left boundary index
 * @param {number} right - Right boundary index
 * @return {TreeNode} - Root of the subtree
 */
function buildTree(nums, left, right) {
  // Base case: no elements to process
  if (left > right) {
    return null;
  }

  // Find the middle element
  const mid = Math.floor((left + right) / 2);

  // Create the root node with the middle value
  const root = new TreeNode(nums[mid]);

  // Recursively build left and right subtrees
  root.left = buildTree(nums, left, mid - 1);
  root.right = buildTree(nums, mid + 1, right);

  return root;
}

Walking Through an Example

Consider the sorted array [-10, -3, 0, 5, 9]. Let us trace through the algorithm:

The middle index is 2, so 0 becomes the root.
The left subarray is [-10, -3]. The middle index is 1, so -3 becomes the left child of the root.
The left subarray of -3 is [-10], so -10 becomes the left child of -3.
The right subarray of the root is [5, 9]. The middle index is 4, so 9 becomes the right child of the root.
The left subarray of 9 is [5], so 5 becomes the left child of 9.

The resulting tree looks like this:

This tree is height-balanced, as the depth difference between any node's left and right subtrees is at most one.

Verifying the Solution

To ensure our solution works correctly, we should write a helper function to traverse the tree and verify its structure. An in-order traversal of a BST should produce the original sorted array.

/**
 * Performs an in-order traversal of the BST.
 * @param {TreeNode} root - Root of the tree
 * @return {number[]} - Array of values in sorted order
 */
function inOrderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (node === null) return;
    traverse(node.left);
    result.push(node.val);
    traverse(node.right);
  }

  traverse(root);
  return result;
}

// Test the solution
const nums = [-10, -3, 0, 5, 9];
const bst = sortedArrayToBST(nums);

console.log('In-order traversal:', inOrderTraversal(bst));
// Output: [-10, -3, 0, 5, 9]

console.log('Root value:', bst.val);
// Output: 0

console.log('Left child:', bst.left.val);
// Output: -3

console.log('Right child:', bst.right.val);
// Output: 9

Handling Edge Cases

A robust solution must handle several edge cases gracefully:

Empty array: Return null immediately.
Single element: Return a tree with just the root node.
Two elements: The first element becomes the root, and the second becomes its right child.
Duplicate values: The algorithm still works, though the resulting tree may not be a strict BST depending on how duplicates are handled. Typically, duplicates are placed in the right subtree.

// Edge case: empty array
console.log(sortedArrayToBST([]));
// Output: null

// Edge case: single element
const single = sortedArrayToBST([42]);
console.log(single.val);
// Output: 42
console.log(single.left, single.right);
// Output: null null

// Edge case: two elements
const two = sortedArrayToBST([1, 2]);
console.log(two.val, two.right.val);
// Output: 1 2

Time and Space Complexity Analysis

Understanding the complexity of our solution is crucial for evaluating its efficiency.

Time Complexity

The time complexity is O(n), where n is the number of elements in the array. Every element is visited exactly once to create a corresponding tree node. The recursive calls divide the array into halves, but since each element is processed only once, the total work is linear.

Space Complexity

The space complexity has two components. First, the recursion stack uses O(log n) space in the best case because the tree is balanced, meaning the recursion depth is proportional to the height of the tree. Second, the output tree itself requires O(n) space to store all n nodes. Therefore, the overall space complexity is O(n).

Alternative Approach: Iterative Solution

While the recursive solution is elegant and easy to understand, an iterative approach can be useful in environments where recursion depth is a concern. The iterative solution uses a stack to simulate the recursive calls.

function sortedArrayToBSTIterative(nums) {
  if (!nums || nums.length === 0) {
    return null;
  }

  const root = new TreeNode(0);
  const stack = [
    {
      node: root,
      left: 0,
      right: nums.length - 1
    }
  ];

  while (stack.length > 0) {
    const { node, left, right } = stack.pop();
    const mid = Math.floor((left + right) / 2);
    node.val = nums[mid];

    if (left <= mid - 1) {
      node.left = new TreeNode(0);
      stack.push({ node: node.left, left: left, right: mid - 1 });
    }

    if (mid + 1 <= right) {
      node.right = new TreeNode(0);
      stack.push({ node: node.right, left: mid + 1, right: right });
    }
  }

  return root;
}

This iterative version produces the same balanced BST but avoids potential stack overflow issues for very large arrays. However, it is more verbose and slightly harder to read than the recursive version.

Best Practices

When implementing this solution, keep the following best practices in mind:

Choose the middle element carefully: Using Math.floor((left + right) / 2) is standard, but for very large arrays, consider left + Math.floor((right - left) / 2) to avoid integer overflow, although JavaScript handles large numbers differently than languages like Java or C++.
Keep functions pure: The recursive helper should not modify the input array. It only reads from it, which makes the function predictable and easy to test.
Validate input: Always check for null or undefined inputs before processing. This prevents runtime errors and makes your code more defensive.
Prefer recursion for readability: Unless you have a specific reason to avoid recursion, the recursive solution is clearer and more maintainable.
Test thoroughly: Write tests covering empty arrays, single elements, even-length arrays, odd-length arrays, and arrays with negative numbers.

Common Mistakes to Avoid

Using the wrong middle index: Forgetting to use Math.floor can result in a non-integer index, causing unexpected behavior.
Incorrect base case: Using left >= right instead of left > right will skip elements when the subarray has exactly one element.
Modifying the array: Slicing the array with Array.slice() at each step increases time complexity to O(n log n) due to copying. Using index boundaries is more efficient.
Forgetting to return the node: In the recursive helper, always return the constructed node so it can be linked to its parent.

Conclusion

Converting a sorted array to a balanced binary search tree is a fundamental problem that beautifully illustrates the divide-and-conquer technique. By consistently selecting the middle element as the root and recursively processing the left and right halves, we can construct a height-balanced BST in O(n) time. The recursive solution is concise and readable, while the iterative alternative offers a stack-safe option for large inputs. Understanding this problem deepens your knowledge of tree structures, recursion, and algorithm design, making it an essential skill for any JavaScript developer tackling data structure challenges. With the implementation, edge case handling, and best practices covered in this guide, you are well-equipped to solve this problem confidently in both interviews and real-world applications.