Binary Search Tree - this.root

[ugwen]

could anyone explain why the code:
delete(value){ this.root = this.deleteNode(this.root, value) }
isn’t actually changing the root node in the tree when it refers to this.root. it is removing a leaf node, as desired, but i don’t understand why it doesn’t break the tree by reassigning it’s root.
(sorry, this is not following the excercise so code is incomplete)

  **Your code so far**

.......

delete(value){
  this.root = this.deleteNode(this.root, value)
}
deleteNode(node, value){
  if(node === null){return node}
  if(value < node.value){
    node.left = this.deleteNode(node.left, value)
  }else if(value > node.value){
    node.right = this.deleteNode(node.right, value)
  }else{
    // THREE SCENARIA:
    if(!node.left && !node.right){return null}
    if(!node.left){return node.right}
    else if(!node.right){return node.left}
    // HAS 2 CHILDREN:
    node.value = this.min(node.right)
    node.right = this.deleteNode(node.right, node.value)
  }
  return node
}
}

const tree = new BinarySearchTree()
tree.add(10)
tree.add(5)
tree.add(15)
tree.add(3)
console.log('tree:',tree)
tree.delete(3)
console.log('tree:',tree)

  **Your browser information:**

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/103.0.5060.134 Safari/537.36

Challenge: Data Structures - Delete a Node with Two Children in a Binary Search Tree

Link to the challenge:

freeCodeCamp.org

[kevinSmith]

The root is just a reference (memory address) that is stored in that class, the reference to the first element.

Imagine if you have a phone list, a linked list (to keep things simple). When you see a tornado, you call the person on the post-it note on your fridge. It says “Bob - 555-1212”. You call Bob then he calls Alice. Then Alice calls Dave who calls Eve who calls…

Bob decides he doesn’t want to participate. Is this complicated? No, Bob give you his “Alice” post it note and you put it on the fridge and throw away the “Bob” one.

A tree is two dimensional and a list is one dimensional, but the idea is the same.

[ugwen]

in your analogy my problem was where the post it note is not the root (perhaps it’s eve’s). then why do i assign this.root in the process of deleting eve’s post-it. i suppose if i was assigning the whole tree accounting for the deletion i could understand. but is that what it is doing? it seems to define/follow the path from the root to the deleted/replaced node. the other memory addresses hold true? or am i missing something about the nature of the this.root assignment?

[ugwen]

I’m thinking it’s the latter, i am missing something…the root is assigned to a function, not a value. the function traverses and deletes whatever…and then this.root is left unchanged, not actually re-assigned. although there are contents which are re-assigned. so i guess it is re-assigned. oh, am i getting somewhere? it’s just if it is re-assigned but the whole tree is not defined in this function, i’m feeling a tad lost.

[snowmonkey]

First question to consider, what does deleteNode take in as its parameters, and what does it return based on those parameters?

Incoming, it has two values: a “reference node,” and a node to delete. And what is returned? Either the original reference node, or null. That’s what you’ll get back.

But if the function returns that original reference node, it performs a recursive call. It checks whether the right or left of the reference node is the one to be deleted, by calling deleteNode again - this time passing in each “child node” as the reference node.

Eventually, this deleteNode will have touched each node that will be kept, and one that will be deleted. In each “kept” case, it returns the reference node. In the one deleted case, it returns null.

By returning null, that particular node and all its descendants have been pruned from the tree.

So when we call

this.root = deleteNode(this.root, value)

What we are doing is calling the deleteNode function on the root, which starts that series of recursive calls. If it isn’t the one to delete, what we’re doing is this.root = this.root, only after scanning all descendants of root to find the one within it to prune.

[ugwen]

so it writes each node it touches, starting with root, to the stack, including rearrangments, then unwinds the stack back to this.root=this.root ?
so its reassigning some nodes, including some without changes, but the tree otherwise is unaffected?

[snowmonkey]

Each node will be tested, either from the this.deleteNode(this.root, value) or from the this.deleteNode(this.right, value) - the call to the current node, or the call to test each of its child nodes.

Based on the result of that test, the given node will either be set right back to itself, or to null.

So yes - using recursion, it drills down into the “leaf nodes” (those with no children), and then unwinds back to the root. Each node in turn is tested, and either kept or pruned as needed.

If the node we had wanted to delete was the root? We’d prune the entire structure. We wouldn’t test any of the other nodes, as that test would immediately have returned null, setting this.root = null;

As that is not the test case you’ve given in tree.delete(3), that is not what happens. In that case:

tree.root = tree.deleteNode(tree.root, 3);

// now that function tests each of the root's `left` and `right`
root.left = tree.deleteNode(root.left, 3);
root.right = tree.deleteNode(root.right, 3);

// So in each of those, `node` is set to `root.left` or `root.right`.
root.left.left = tree.deleteNode(root.left.left, 3)
root.left.right = tree.deleteNode(root.left.right, 3)
// That tested both of the "left" descendant's children.
// let's imagine that root.left.right had a value of 3.
// We would continue each branch...
root.right.left = tree.deleteNode(root.right.left, 3);
root.right.right = tree.deleteNode(root.right.right, 3)

// now, from those last four, we get these:
root.left.left = root.left.left;
root.left.right = null; // <--- SEE WHAT HAPPENED HERE?
root.right.left = root.right.left;
root.right.right = root.right.right;

// and those "unwind" to their ancestors:
root.left = root.left;
  // but again, root.left contains `left`, `right`, both of which we just set! 
root.right = root.right;

// and final unwind. remember, root contains `root.left` and `root.right`,
//  so we are getting them automagically!
root = root;

So yes - we drill in, testing each node except for those within the one we’re pruning. Those we don’t need to test, as we remove them by pruning the parent. And for each node, we either return that node, or we return null.

And what are we returning to? To the parent, who called this.deleteNode() on this child in the first place. That’s the recursion, and that’s how it “unwinds.”