In order traversal DFS

1

I do not understand how/why its pushing 4

whats causing that function to be called again? here is the relevant code:

 inOrder() {
    if (this.root == null) {
      return null;
    } else {
      var result = new Array();
      function traverseInOrder(node) { 
        console.log("node=",node)
        node.left && traverseInOrder(node.left);
        console.log("pushing node data", node.data)
        result.push(node.data);
        // console.log("node.right=",node.right)
        console.log("node after$$$$=",node)
        // console.log("this.root",this.root)
        node.right && traverseInOrder(node.right);
      }
      console.log('hi')
      traverseInOrder(this.root);
      return result;
    };
  }

everything up until where it pushes in 4 makes sense. The way I am expecting it to behave: it goes all the way to the left of the tree and pushes 3. the node with data of 3 has no right prop, so the last line of that function definition will result to false and never be executed.

what is causing traverseInOrder to be called again?

additionally even if it is called again .push does not mutate the tree (it never removes the node with the data prop of three from the tree) . it only copies over the value of 3 to the holder. please explain this to me.

edit: here is the tree:

tree
tree975Ă—796 56.1 KB

2

It’s hard to say for sure without seeing the entire code (we do not see the way the tree is setup or what this.root is in the snippet you’ve provided, but assuming the tree is setup correctly as represented by the tree diagram you’ve provided and that this.root is the root node from that diagram (node 9), here are my answers:

Remember this traversal is implemented in a recursive fashion. When the function is called passing the node with value 3 it is already two calls deep into the calls stack:

// (Conceptual) Call Stack
// traverseInOrder(node 9) <-- Initial call
//    traverseInOrder(node 4) <-- first recursive call
//         traverseInOrder(node 3) <-- second recursive call

So as it’s processing node 3:

  1. it’s left is null, so it will not call traverseInOrder(node.left)
  2. the node 3 gets pushed onto result
  3. it’s right is null, so it will not call traverseInOrder(node.right)
  4. At this point it makes it to the end of the function and execution resumes at the call stack where node 4 was passed, from where it left off in the function (which is just after the call to traverseInOrder(node.left))
  5. the node 4 gets pushed onto result
  6. At this point node 4 has a right so it calls traverseInOrder(node.right)

…and this continues on until all nodes in the tree have been visited…

The important thing to remember is that for each recursive call a new entry is added to the call stack, and when each node is completely processed the function will reach the end, pop off the call stack, and resume with the previous entry on the call stack.

A good way to visualize this is to use the debugger in Developer Tools. I’d suggest running this example in the browser adding a “debugger” statement just before the initial call to traverseInOrder so that you can walk through the code, paying attention to the call stack as you step through the code.

I’m not sure why you are expecting the tree to be mutated. In order to remove node 3 from the tree you would have to set node 4’s left to null. Since your function is just called traverseInOrder I would just expect it to traverse the tree, as it is doing, and not actually mutate it.

1 Like
3

I wasn’t expecting it to be mutated, nevermind that. I will explain:

And this is the line I needed to help me understand it, I already knew about the function calls piling on top of each other on the stack and popping off one at a time as they return, and being garbage collected as if they are like local variables… my sticking point was in realizing that they would continue at the exact point from where they had last left off.

because you see node 4 also has a left, but like you said it had already passed that part in the code prior.

thank you as that line is exactly what i needed. and yes I confirmed what you said with debugger. So i agree with the explanation 100%

1 Like