How does in-order traversal in Binary search tree works (recursion) 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 &lt; 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?
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.