CODEWITHSUNDEEP
javascriptalgorithmbinary-search-tree
Xinrui Ma
Xinrui Ma

Reputation: 2105

Code failed to create BST with array of numbers

I try to create a BST with the following code, nums = [4,5,8,2]

var TreeNode = function (val) {
    this.val = val;
    this.left = this.right = null;
    this.count = 1;
}

var constructBST = function(nums) {
    if (nums.length === 0) return null;
    let root = new TreeNode(nums[0]);
    for (let i = 1; i < nums.length; i++) {
        let currentNode = root;
        while (currentNode) {
             if (currentNode.val > nums[i]) {
                currentNode = currentNode.left;
            } else if (currentNode.val < nums[i]) {
                currentNode = currentNode.right;
            }
        }
        currentNode = new TreeNode(nums[i]);
    }
    console.log(root);
    return root;
}

I take root as current node for each iteration, and move the currentNode based on the value, but when I print out the root after I iterate the array, why my root node doesn't change?

This is the output:

TreeNode { val: 4, right: null, left: null, count: 1 }、

Edit: say if I have a root node 3, and it has no child, when I set current node to root, and if I move currentNode = currentNode.left; Doesn't this mean there is a connection between currentNode and the root? I thought the currentNode would now represent root's left child. If I make any changes to currentNode, the root's left child would also change

Upvotes: 2

Views: 56

Answers (1)

Codor
Codor

Reputation: 17605

You seem to be navigating the tree correctly, but the newly created nodes are never connected to their intended parent. Change the function as follows.

var constructBST = function(nums) {
    if (nums.length === 0) return null;
    let root = new TreeNode(nums[0]);
    for (let i = 1; i < nums.length; i++) {
        let currentNode = root;
        while (currentNode) {
             if (currentNode.val > nums[i]) {
                if (null == currentNode.left) {
                    currentNode.left = new TreeNode(nums[i]);
                    currentNode = null;
                } else {
                    currentNode = currentNode.left;
                }
            } else if (currentNode.val < nums[i]) {
                if (null == currentNode.right) {
                    currentNode.right = new TreeNode(nums[i]);
                    currentNode = null;
                } else {
                    currentNode = currentNode.right;
                }
            }
        }
    }
    console.log(root);
    return root;
}

Upvotes: 2

Related Questions