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?