How does in-order traversal in Binary search tree works (recursion)

Question

I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript.

The code is typical BST implementation with methods to support in-order traversal. The code that is the most relavant for this question is the the inOrderTraverse and inOrderTraverseNode. I cannot understand how this code work.

function BinarySearchTree() {

    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    };

    var root = null;

    this.inOrderTraverse = function (callback) {

         inOrderTraverseNode(root, callback);
    }


    this.insert = function (key) {


        var newNode = new Node(key);

        if (root === null) {
            root = newNode;
        }
        else {
            insertNode(root, newNode);
        }

    }


    var insertNode = function (node, newNode) {

        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }

    };


    var inOrderTraverseNode = function (node, callback) {

        if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    }
}

The code that will use the BinarySearchTree "class".

function printNode(value) {
    document.writeln(value);
}


var tree = new BinarySearchTree();

tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);

tree.inOrderTraverse(printNode);

This will generate a BST like this:

taken from the book Learning Javascript Data Structure and Algorithms by Loiane Grone

I will explain how I think the in-order functionality works.

    var inOrderTraverseNode = function (node, callback) {

    if (node !== null) {     //checks if the node is null, 11 is not null so it continues
        inOrderTraverseNode(node.left, callback);     //keep executing this code until it finds a node with left null
        callback(node.key);      //3, the node with left null is printed
        inOrderTraverseNode(node.right, callback);     // checks if the 3 node has a right node, it doesn't have, so the execution finishes
    }

}

11 the root node is passed to the inOrderTraverseNode, it checks to see if the left is a null, if it is not it continues passing the left node until the left node is null. When a left null node is found Then it prints the value, callback(node.key) will execute as callback(3), so the 3 will be the first item printed on the screen. The execution then continues to inOrderTraverseNode(node.right, callback), 3 don't have a right child so execution will go on and that's that.

in my mind the output would be 3 only.

How do the in-order traversal get from 3 to the 5?

Answer 1

The important part is to consider the entire call stack.

When you're calling inOrderTraverseNode on the root, what happens first is it calls it on its left child, and so on.

So at the point that we call it on 3, the call stack above us looks like

inOrderTraverseNode(Node(11), callback)
 inOrderTraverseNode(Node(7), callback)
  inOrderTraverseNode(Node(5), callback)
   inOrderTraverseNode(Node(3), callback)

Eventually, the inOrderTraverseNode on the node with value 3 returns (after calling it on the null children).

At this point, the current point in code execution is at:

  if (node !== null) {     //checks if the node is null, 11 is not null so it continues
      inOrderTraverseNode(node.left, callback);     //keep executing this code until it finds a node with left null
    > callback(node.key);      //3, the node with left null is printed
      inOrderTraverseNode(node.right, callback);     // checks if the 3 node has a right node, it doesn't have, so the execution finishes
  }

But now the node in question is 5, we've returned back up a level, so the stack is:

inOrderTraverseNode(Node(11), callback)
 inOrderTraverseNode(Node(7), callback)
  inOrderTraverseNode(Node(5), callback)

So the callback is called on 5, and now we continue execution, recursively traversing the right subtree. After that, that code returns, and eventually we have the stack:

inOrderTraverseNode(Node(11), callback)
 inOrderTraverseNode(Node(7), callback)

And now we're finished with the left subtree, so we call the callback with 7.

And so on. So imagine the stack growing every time you call it on a subtree. Then you go back up, process that node, then head back down to the other subtree (growing the stack again), and processing that.

So what you're neglecting from your explanation is that after execution finishes, it goes back to the code that called it. So although it makes it down to 3, and processes fully there, that code was called from the call at 5, so it has to finish processing that call. Likewise for each further call up. This is the same process that brings you back to where you were after you call it.

Answer 2

Consider indorder as a command in military. Let the binary tree be the hierarchy among the soldiers.

The general shouts "inorder!" and that means, when a subordinate receives the order, he tells it to his "left" subordinates. If he has no subordinates on the left side, then he yells out his name, and only then he commands his right subordinate to execute the order.

Inorder! command means "tell your first subordinate, do it yourself, and then tell your right subordinate. Afther you are finished, report to your superior."

The general is the root of the binary tree. He shouts out "inorder!"

That means his left subordinate gets the order, and shouts out "inorder!" himself. This process goes on until the order reaches to a soldier who has no left subordinate. Then, he yells out his name and gives the order to his right subordinate.

After all his right subordinates are done, he reports back to his immediate superior. The superior, like him, yells out his name and gives the order to his right subordinate.

When all the left side is done, the general (root of the binary tree) yells out his name and gives the order to his right side.

Now, consider this tree
(taken from https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/):

The general is 1. He shouts "inorder!"

2 recieves the order, and he shouts "inorder!"

4 receives the order. He has no left child, and thus shouts his name: 4

He has also no right child, and thus reports to 2.

Left side of 2 is done, and this 2 shouts his name: 2, and then gives the order to the right side.

This process goes on, until the root is notified a second time.