Understand JavaScript Recursion and Call Stack in Depth First Traversal

Well, your explanation leaves some important steps out, and I think that's allowing you to reach some invalid conclusions. In particular, the stack never looks like

traverse(TreeNode(7))       
traverse(TreeNode(6))       
traverse(TreeNode(5))       
traverse(TreeNode(4))       
traverse(TreeNode(3))       
traverse(TreeNode(2))       
traverse(rootNode)          

For the record, none of this is javascript-specific; so really I think this is about improving how well you understand recursion.

Let's step through your traverse(rootNode) call in more detail. So of course the call stack starts out like

0: traverse ( node = rootNode ) {
|  =>  if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|      }
|      if(node.right){
|          traverse(node.right)
|_     }

Here I'm using notation that makes a few things more explicit:

• I put a number before the call; this way, for example, I could refer to the above call as "call 0 on the stack"
• I show the parameter assignments of each call
• I show the code of the function behind each call, with an arrow => indicating current progress through the code for this particular call. Here we're about to execute the first instruction.

Following the convention you appear to be using, the most recently-pushed (next-to-pop) item will be shown at the top.

So now since node is rootNode and that's not null, it doesn't just immediately return. Before any recursion starts, it calls visit() on rootNode, which goes ahead and prints 1. This is one of the things that seems missing from your explanation - nodes are visited (and their values printed) before any recursion, so they're being printed as you traverse, as you first reach each node.

Then it checks the left and finds a truthy value (in this case, another node object), so it calls traverse(node.left) and we end up with a stack like

1: traverse ( node = node_A )
|  =>  if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|      }
|      if(node.right){
|          traverse(node.right)
|_     }

0: traverse ( node = rootNode ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|  =>  }
|      if(node.right){
|          traverse(node.right)
|_     }

So again we start executing traverse() from the beginning with our new node value, which is not null so we go ahead and visit(node) - which, since node is node_A, prints 2. Then it checks left, which is truthy (node_C) and we get

2: traverse ( node = node_C )
|  =>  if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|      }
|      if(node.right){
|          traverse(node.right)
|_     }

1: traverse ( node = node_A ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|  =>  }
|      if(node.right){
|          traverse(node.right)
|_     }

0: traverse ( node = rootNode ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|  =>  }
|      if(node.right){
|          traverse(node.right)
|_     }

node_C isn't null, so it gets visit()ed and this prints 3. Now we check left, but it's falsey (undefined). So we check right and it, too, is falsey (undefined). So we return and now the stack says

1: traverse ( node = node_A ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|  =>  }
|      if(node.right){
|          traverse(node.right)
|_     }

0: traverse ( node = rootNode ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|  =>  }
|      if(node.right){
|          traverse(node.right)
|_     }

Now we're already midway through the traverse() code for call 1 on the stack, so we pick up where we left off (at the =>). So now we check right, which is truthy and we get

2: traverse ( node = node_D )
|  =>  if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|      }
|      if(node.right){
|          traverse(node.right)
|_     }

1: traverse ( node = node_A ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|      }
|      if(node.right){
|          traverse(node.right)
|_ =>  }

0: traverse ( node = rootNode ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|  =>  }
|      if(node.right){
|          traverse(node.right)
|_     }

Now visit will print 4 (because node is node_D, and both left and right are falsey, so we return to

1: traverse ( node = node_A ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|      }
|      if(node.right){
|          traverse(node.right)
|_ =>  }

0: traverse ( node = rootNode ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|  =>  }
|      if(node.right){
|          traverse(node.right)
|_     }

But call 1 on the stack has reached the end of it's code, so it returns and we go to

0: traverse ( node = rootNode ) {
|      if (node == null) return
|      visit(node)
|
|      if(node.left){
|          traverse(node.left)
|  =>  }
|      if(node.right){
|          traverse(node.right)
|_     }

Call 0 picks up where it left off, which means it's about to check right (which, I think, answers your original question). Execution proceeds down the right branch in exactly the same way it proceeded down the left, with the stack at various times containing calls for rootNode, node_B, then rootNode, node_B, node_E, then rootNode, node_B again (but with the code partially executed), then rootNode, node_B, node_F, then one last time rootNode, node_B (with the code about to finish), then back to rootNode, and then the initial call to traverse finally returns.