Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #35934 > unrolled thread

Not understanding this code (Binary trees)

Back to article view | Back to comp.lang.javascript

Contents

  Not understanding this code (Binary trees) groovee@cyberdude.com - 2018-12-26 00:07 -0800
    Re: Not understanding this code (Binary trees) "R.Wieser" <address@not.available> - 2018-12-26 10:39 +0100

#35934 — Not understanding this code (Binary trees)

OK, so in my JS book, there is this code under "Removing a node (from a Binary tree)":

var removeNode = function (node, key) {

    if (node === null) {
        return null;
      }

if (key < node.key) {
     node.left = removeNode(node.left, key); //{1}
     return node;
}

...blah blah


I'm not being able to understand this.
Assume that key IS less than node.key to begin with. So it gets to the "node.left = ..." line (line 1) and then STARTS EXECUTING "remove.Node" FROM THE BEGINNING AGAIN *WITHOUT "remove.Node" EVER GETTING TO THE "return node" LINE, ie. without the function ever *returning anything*, right....?!!! Let alone anything ever getting assigned to "node.left"...? So how can this code work??

[toc] | [next] | [standalone]

#35935

Groovee,

> So how can this code work??

Its called recursion.

Removing a node does not only mean that the first-found smaller node needs 
to be removed, but also all nodes left of it (meaning: smaller than it). 
If you don't you may not be able to access those nodes anymore, but all 
their resources would still be there in memory.   In other words, you would 
be "bleeding memory".

> So it gets to the "node.left = ..." line (line 1) and then
> STARTS EXECUTING "remove.Node" FROM THE
> BEGINNING AGAIN

Nope.    Look at the function itself : "var removeNode = function (node, 
key)".  That "node" argument defines where to start.   Now take a look at 
the "node.left = removeNode(node.left, key);" call inside it.  The new 
starting point is "node.left", which is the left-side leaf of he current 
node.   Which definitily is *not* the whole tree. :-)

> ie. without the function ever *returning anything*, right....?!!!

No, not quite.   It would dive (recursing) into the left-side subtree until 
it doesn't find a leaf-node anymore.   That is when the " if (node === 
null)" comparision kicks in and it starts to walk back - but again diving 
into a subtree if/when it finds one.

In the end it will have arrived at he first node it wanted to delete.

Hope that clarifies it a bit.

Regards,
Rudy Wieser

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.javascript

csiph-web