CODEWITHSUNDEEP
javascriptalgorithmdata-structuresbinary-search-tree
Jermain Singleton
Jermain Singleton

Reputation: 15

Binary Search Tree javascript Array - Data Structures

I am trying to build a binary tree with a array. I want to take the array, find the root and split right and left side, then perform the same split on each side if needed until two numbers are left and the lowest goes left and the highest goes right. The left side numbers will be lower than the right side numbers.

I have rewrote code in the past day to 2 different versions I erased what I had prior. Still a bit unsure but both are working

Version 1 - This is my working version i am moving forward with. I tried to do this tons of ways and had a break through last night.

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree{
    constructor(arr){
        this.arr = arr
        this.root = null
    }

    buildtree(arr) {

        console.log(arr)
        if (arr.length <= 0) { return null } 

        let mid = Math.floor(arr.length / 2)
        let root = new Node(arr[mid])
        
        root.left = this.buildtree(arr.slice(0, mid))
        root.right = this.buildtree(arr.slice(mid + 1))
        
        return root
    }

    insert(value){

        console.log(value)
        return "this is working"
    }
    

}

//const arr = [1, 2, 3, 4, 5, 6, 7]
let arr = [1, 7, 4, 23, 8, 9, 4, 3, 5, 7, 9, 67, 6345, 324]
const bst = new BinarySearchTree(arr)
console.log(bst.buildtree(arr))

Html code below

<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width">
    <script type="module" src="myscript.js"></script>
    
    <title>Test</title>
  </head>

  <body>
    
    
  </body>

</html>

version 2

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(arr){
        this.arr = arr
        this.root = null
    }

    buildtree(arr) {

        if (arr.length <= 0) { return null} 

        let root = this.root
        //console.log(root)  null
        let mid = Math.floor(arr.length / 2)
        //console.log(nums[mid])3-just mid and 4-mid nums

        root = new Node(arr[mid])
        //console.log(root)

        let lSide = arr.slice(0, mid)
        console.log(lSide, "left side, unused")

        let rSide = arr.slice(mid  + 1, arr.length)
        console.log(rSide, "right side unused")
        
        console.log(lSide.length, rSide.length)
         //while there is something in the queue of each mini array

        //total length of array to use as a counter
        let totalLength = lSide.length + rSide.length
        console.log(totalLength)


        for(let i = 0; i <= lSide.length; i++){
           //console.log(i) I got 7 loops through

            //if left side greater 3 and not = null
            if (lSide.length >= 3){
                //Get the middle of the left side
                let lMid = Math.floor(lSide.length / 2)
                //console.log(lMid)
                let parent = new Node(lSide[lMid])
                //console.log(root)
                //console.log(parent)
                root.left = parent  
                //console.log(lSide)
                //console.log(lSide)
            } 
            if (lSide.length <= 3){
                if(lSide[0] < lSide[2]){
                
                    //create a node for leaf 
                    let childL = new Node(lSide[0])
                    let childR = new Node(lSide[2])
                    //set parent node to left
                    let parent = root.left
                    //assign the chile node
                    parent.left = childL
                    parent.right = childR
                    
                } else{
                    
                    let childR = new Node(lSide[0])
                    let childL = new Node(lSide[2])
                    let parent = root.right
                    parent.right = childR
                    parent.left = childL
                    
                } 
            } else{
                //console.log(root.left)
                let mid = Math.floor(lSide.length / 2)
                let lmid = lSide[mid]
                //console.log(lmid)
                let leftSplits = lSide.slice(0, mid)
                let rightSplits = lSide.slice(mid + 1, lSide.length)
                //console.log(leftSplits)
                //console.log(rightSplits)
                //console.log(root.left)
                let parent = root.left
                let midl = Math.floor(leftSplits.length / 2)
                let midr = Math.floor(rightSplits.length / 2)
                let childL = new Node(leftSplits[midl])
                parent.left = childL
                let childR = new Node(rightSplits[midr])
                parent.right = childR

                childL.left = leftSplits[0]
                childL.right = leftSplits[2]
                childR.left = rightSplits[0]
                childR.right = rightSplits[2]
            }

            
            for(let j = 0; j <= lSide.length; j++){
                
                if(rSide.length >= 3){
                    //Get the middle of the left side
                    
                    let rMid = Math.floor(rSide.length / 2)
                    //console.log(rMid)

                    //let mid = Math.floor(arr.length / 2)

                    let mid = rSide[rMid]
                    //console.log(mid)
    
                    let parent = new Node(mid)
                    //console.log(parent)

                    root.right = parent
                   //console.log(parent)
                   
                }
                
                  if (rSide.length <= 3){

                    

                    if(rSide[0] < rSide[2]){
                        let childL = new Node(rSide[0])
                        //console.log(childL)
                        let childR = new Node(rSide[2])
                        //console.log(childR)

                        let parent = root.right
                       // console.log(parent)

                        parent.left = childL
                        //console.log(parent.left)
                        parent.right = childR
                        //console.log(parent.right)

                    } else{
                        //console.log("another test")
                        let childR = new Node(rSide[0])
                        let childL = new Node(rSide[2])
                        let parent = root.right
                        parent.right = childR
                        parent.left = childL
                    } 
                } else {
                    //console.log(root.left)
                let mid = Math.floor(rSide.length / 2)
    
                
                let leftSplits = rSide.slice(0, mid)
                let rightSplits = rSide.slice(mid + 1, rSide.length)
                //console.log(leftSplits)
                //console.log(rightSplits)
                //console.log(root.left)
                let parent = root.right
                let midl = Math.floor(leftSplits.length / 2)
                let midr = Math.floor(rightSplits.length / 2)
                let childL = new Node(leftSplits[midl])
                parent.left = childL
                let childR = new Node(rightSplits[midr])
                parent.right = childR

                childL.left = leftSplits[0]
                childL.right = leftSplits[2]
                childR.left = rightSplits[0]
                childR.right = rightSplits[2]
                }
           }
        }
        return root
        
    }//funct
} //class


//const nums2 = [1, 2, 3, 4, 5, 6, 7]
const nums2 = [1, 7, 4, 23, 8, 9, 4, 3, 5, 7, 9, 67, 6345, 324]
const bst = new BinarySearchTree(nums2)
//console.log(root.nums)
console.log(bst.buildtree(nums2))

They both work and I was thinking version #2 is not recursive but not sure

Upvotes: -2

Views: 90

Answers (1)

Subhan Amjad
Subhan Amjad

Reputation: 22

To build a binary search tree (BST) from a sorted array, we can recursively choose the middle element of the array as the root node, and then recursively build the left subtree from the left half of the array and the right subtree from the right half. Your logic is on the right track, but there are a few issues with your approach, particularly with the recursive structure.

The key to solving the problem is:

Use the middle element of the array as the root. Recursively divide the left and right subarrays and assign them as the left and right children of the current node. Base case: if the array has 1 or 2 elements, handle them appropriately by ensuring the smaller value goes to the left and the larger one to the right.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(nums) {
        this.nums = nums;
        this.root = this.buildtree(nums);
    }

    buildtree(nums) {
        // Base case: If no elements, return null
        if (nums.length === 0) return null;

        // Find the middle element of the array
        let mid = Math.floor(nums.length / 2);
        let node = new Node(nums[mid]);

        // Recursively build the left and right subtrees
        node.left = this.buildtree(nums.slice(0, mid)); // Left subarray
        node.right = this.buildtree(nums.slice(mid + 1)); // Right subarray

        return node; // Return the current node (root of the subtree)
    }
}

// Test the implementation
const nums = [1, 2, 3, 4, 5, 6, 7];
const bst = new BinarySearchTree(nums);

// Function to print the tree structure (for testing)
function printTree(node, level = 0) {
    if (node !== null) {
        printTree(node.right, level + 1);
        console.log(" ".repeat(4 * level) + "-> " + node.value);
        printTree(node.left, level + 1);
    }
}

printTree(bst.root);

Upvotes: 0

Related Questions