Implementing a Binary Search Tree using JavaScript Arrays

Other Questions JavaScript
1

I’m working on creating a binary search tree from an array in JavaScript. My goal is to find the root, split the array into left and right sides, and repeat this process until only two numbers remain. The smaller number goes to the left, while the larger one goes to the right. The numbers on the left side are always lower than those on the right side.

I’ve developed two versions that both work:

class TreeNode {
  constructor(data) {
    this.data = data;
    this.leftChild = null;
    this.rightChild = null;
  }
}

class BST {
  constructor(dataArray) {
    this.dataArray = dataArray;
    this.rootNode = null;
  }

  createTree(data) {
    if (data.length === 0) return null;

    const middleIndex = Math.floor(data.length / 2);
    const rootNode = new TreeNode(data[middleIndex]);

    rootNode.leftChild = this.createTree(data.slice(0, middleIndex));
    rootNode.rightChild = this.createTree(data.slice(middleIndex + 1));

    return rootNode;
  }
}

const numbers = [2, 8, 5, 1, 10, 3, 7, 4, 6, 9];
const binarySearchTree = new BST(numbers);
console.log(binarySearchTree.createTree(numbers));

This version is recursive. However, I’m not sure if my second version is recursive or not. Both versions work, but I’m curious about which approach might be more effective. Any suggestions for improvements?

2

From my experience with BSTs in JavaScript, I’d say your recursive approach is more efficient and cleaner. It’s easier to understand and maintain. However, for very large datasets, you might encounter stack overflow issues. In such cases, an iterative method could be preferable.

One suggestion to improve your implementation: consider pre-sorting the input array. This ensures a balanced tree, which can significantly enhance performance, especially for search operations.

Also, keep in mind that array-based implementations, while conceptually simpler, aren’t as efficient for frequent insertions and deletions compared to traditional pointer-based implementations. If you anticipate regular modifications to the tree after creation, you might want to explore a node-based approach instead.

Lastly, don’t forget to handle edge cases, particularly duplicate values in your input array. Depending on your specific requirements, you may want to either discard duplicates or implement a consistent strategy for handling them.

3

yo, ur recursive method looks solid. iterative can be faster for big datasets tho. have u thought bout balancing? might wanna check out AVL trees or Red-Black trees for that. they keep things balanced n quick. just a thought from my experience

4

I’ve implemented binary search trees using arrays in JavaScript before, and I can share some insights from my experience. While both approaches you’ve shown work, the recursive method is generally more elegant and easier to understand. It naturally follows the divide-and-conquer principle inherent in BSTs.

However, for very large datasets, you might run into stack overflow issues with recursion. In those cases, an iterative approach could be more suitable. One optimization you could consider is pre-sorting the input array. This ensures a balanced tree and improves overall performance.

Another thing to keep in mind is that array-based implementations, while conceptually simpler, aren’t as efficient for insertions and deletions compared to pointer-based implementations. If you’re planning to modify the tree frequently after creation, you might want to consider a more traditional node-based approach.

Lastly, don’t forget to handle edge cases like duplicate values in your input array. Depending on your requirements, you might want to either discard duplicates or implement a strategy to handle them consistently.