Below is the implementation of a BST with an insertion function for it. currently, the code wouldn’t work; It would just spit out Tree { root: null }
When i tried to debug it, it seems that it successfully adds the new Node to the correct spot, but once it returns from the function, all that data is lost and it ends up not inserting anything.
here is the code:
class Node { constructor(value) { this.value = value this.left = null; this.right = null; } } class Tree { constructor() { this.root = null } insert(value) { const insertHelper = (value, node) => { if (node === null) { node = new Node(value) return null } else if (node.value === node.value) { console.log("Value exists.") return null; } else if (node.value < node.value) { return this.insertHelper(node, node.right) } else { return this.insertHelper(node, node.left) } } return insertHelper(value, this.root) } } var tree = new Tree; tree.insert(10) tree.insert(5) console.log(tree);
Advertisement
Answer
Several issues:
this.root
is never modified. Function arguments are passed by value, so if you passthis.root
as argument, and the function assigns a new value to the corresponding parameter variablenode
, this will not affectthis.root
. The solution is to let the helper function return the new value of the node that is passed as argument, so you can assign it back to the root (or other node).At several places you compare
node.value
withnode.value
. That is a mistake. The comparison should involvevalue
.The recursive calls pass
node
as first argument, while the function expects the value as first argument.
Here is the corrected code:
class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } class Tree { constructor() { this.root = null; } insert(value) { const insertHelper = (value, node) => { if (node === null) { node = new Node(value); } else if (node.value === value) { console.log("Value exists."); } else if (node.value < value) { node.right = insertHelper(value, node.right); } else { node.left = insertHelper(value, node.left); } return node; } this.root = insertHelper(value, this.root); } } var tree = new Tree; tree.insert(10); tree.insert(5); console.log(tree);
NB: use semi-colons explicitly. Relying on the automatic semi-colon insertion is asking for trouble. One day it will hit you.