Code failed to create BST with array of numbers

Question

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

The problem seems to be that while you navigate correctly in the tree, the newly created nodes are not actually connected to the tree. — Codor
– Codor, Commented Jun 14, 2018 at 5:13

Codor · Accepted Answer · 2018-06-14 05:19:32Z

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;
}

Collectives™ on Stack Overflow

Code failed to create BST with array of numbers

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related