Javascript: Binary Search Tree in order traversal recursive confusion

Question

given the code below, I am bit confused as to how the order of operations happens to get an in order traversal of a binary search tree.

BinarySearchTree.prototype.inOrder = function() {
    if (this.root == null) {
      return null;
    } else {
      var result = new Array();
      function traverseInOrder(node) {       
        node.left && traverseInOrder(node.left);
        result.push(node.data);
        node.right && traverseInOrder(node.right);
      }
      traverseInOrder(this.root);
      return result;
    };
}

I tried to add a debugger statement and follow but I get lost inside:

  function traverseInOrder(node) {       
    node.left && traverseInOrder(node.left); //step 1
    result.push(node.data);  //step 2
    node.right && traverseInOrder(node.right); //step 3
  }

node.left && traverseInOrder(node.left); (Step 1) gets run then gets run again then gets run again. Finally when there is no node.left, Step 2 gets called : result.push(node.data);
This is the part where it loses me. Now it tries to run node.right && traverseInOrder(node.right) but there is no node.right but instead of moving out of the function, it goes back up to Step 2, result.push(node.data);.

Is this queued up from the multiple recursive calls in Step 1?

Answer 1

Let's look at an example. Let it be the below tree which will be traversed in order.

• The first traverseInOrder is called with this.root, it means the parameter from the above example is A. The node.left exists, it follows traverseInOrder is called with parameter B.
  • In the call of B the node.left exists, it follows traverseInOrder is called with parameter D.
    • In the call of D node.left does not exist (node.left is falsy), so result.push(node.data); is called with parameter D. In the next step node.right is falsy, it follows the traversInOrder with parameter D is finished. We get back to the B.
  • We are back to call B, and because the traversInOrder with D just finished, result.push(node.data) will be called with parameter B. And as next node.right is truthy so traverseInOrder is called with the node.right so with E.
    • At E node.left is falsy, result.push is called with parameter E. node.right is falsy is the call with E ended here. We get back to call A, because as we return from here to the call of B it finishes at this point.
• At call with parameter A we just finished the left node, result.push(node.data); is called for A and next node.right is truthy so result.push(node.data) is called with the right node witch means parameter C.

And it goes on the same with the C,F,G.