Given an array of integers, nums, sorted in ascending order, your task is to construct a height-balanced binary search tree (BST) from this array.

sorted-array-to-bst.js

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

import { TreeNode } from "./ds_v1/BinaryTree.js";

function sortedArrayToBST(nums) {
  let root = null;
  let current = null;

  nums.forEach((num, index) => {
    const node = new TreeNode(num);
    if (index <= Math.floor(nums.length / 2)) {
      node.left = current;
      current = node;
      // while we are climbing the left side of the tree, we need to update root,
      // since it's changing every time
      root = node;
    } else {
      // here we are going down the right side of the tree, so root is unchanged
      current.right = node;
      current = node;
    }
  });

  // Replace this placeholder return statement with your code
  return root;
}

export { sortedArrayToBST };

// tc: O(n)
// sc: O(1)