Encode sorted array to bst

Question

I am converting array to binary search tree using this approach I get root node which contains all the information about tree. But I want it in format

• The left child of the node at index i is at index 2i + 1
• the right child is at index 2i + 2
• The parent of a node at index i is at index [i−1]/2

Basically output [16, 10, 24, 7, 12, 20, 28, 4, 8, 11].

as this output satisfies

• parent node i =0 16
• left 2*0+1 = 1 (10)
• and right 2*0+2 = 24 so 16>10 && 16<24

so bst property is satisfied. hence true and similarly for other array element

.

/**/
  function TreeNode(val, left, right) {
      this.val = (val===undefined ? 0 : val)
      this.left = (left===undefined ? null : left)
      this.right = (right===undefined ? null : right)
  }

var sortedArrayToBST = function(nums) {
    return createBinary(nums, 0, nums.length-1);
}

function createBinary(nums, start, end) {
    if (start > end) {
        return null;
    }
    const mid = Math.floor((start + end) / 2);
    const root = new TreeNode(nums[mid]);
    root.left = createBinary(nums, start, mid - 1);
    root.right = createBinary(nums, mid + 1, end);
    return root;
}

nums = [4, 7, 8, 10, 11, 12, 16, 20, 24, 28];
const root = sortedArrayToBST(nums);
console.log(root);

Answer 1

Looking at your desired output, it looks like you want to build a complete binary tree, which is just one of the possible shapes a binary search tree could have for the given values. This shape does not necessarily put the "middle" value at the root, so that is not a logic you can apply here.

You can instead use a recursive approach that does not first determine the root, but will only do that when the left subtree has been generated. So you could say, instead of doing a preorder traversal, do an inorder traversal. Also, you don't really need to create the node structure, but can immediately populate the target array.

function createBinaryTree(nums) {
    // If your input is already sorted, you can skip this sort call:
    nums.sort((a, b) => a - b);
    const it = nums.values(); // Iterator over nums
    const tree = []; // Result array
    
    function inorderAssign(j) {
        if (j >= nums.length) return; // There is no child here.
        inorderAssign(j*2 + 1); // Pass the target index of the left child
        tree[j] = it.next().value; // Get the next input value and place it here
        inorderAssign(j*2 + 2); // Pass the target index of the right child
    }
    inorderAssign(0);
    return tree;
}

const nums = [4, 7, 8, 10, 11, 12, 16, 20, 24, 28];
const tree = createBinaryTree(nums);
console.log(...tree);