The easiest way to understand code is usually to try it out with a debugger. Chrome has an excellent debugger which you can use to step through the code, line by line, as it runs in real time.
The next easiest way is to use console logs to print out what's happening, which is how most programmers over a certain age would figure out what was happening before debuggers made it easier.
Since I can't sit next to you with a debugger open, let's do the next best thing and add some console logs so we can see what's happening:
function inOrderHelper(root) {
console.group("Entering inOrderHelper with ", root);
if (root !== null && root !== undefined) {
console.log("Root is not null, so continue");
console.group("Traversing down the left node");
inOrderHelper(root.left);
console.groupEnd();
console.log("The root value is ", root.value);
console.group("Traversing down the right node");
inOrderHelper(root.right);
console.groupEnd();
} else {
console.log("Root is null, so back up");
}
console.log("Exiting inOrderHelper");
console.groupEnd();
}
So let's try an example BST:
Which could be constructed to look something like this in JavaScript:
{
left: {
left: {
value: 1,
},
value: 2,
right: {
value: 3,
},
},
value: 4,
right: {
value: 5,
},
}
You can run this code in your browser's dev tools by pasting in the above function (and hitting enter) and then calling it like so:
inOrderHelper({
left: {
left: {
value: 1,
},
value: 2,
right: {
value: 3,
},
},
value: 4,
right: {
value: 5,
},
})
The result should look something like this:
Entering inOrderHelper with {left: {…}, value: 4, right: {…} }
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with {left: {…}, value: 2, right: {…}}
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with { value: 1 }
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
The root value is 1
Traversing down the right node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
Exiting inOrderHelper
The root value is 2
Traversing down the right node
Entering inOrderHelper with { value: 3 }
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
The root value is 3
Traversing down the right node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
Exiting inOrderHelper
Exiting inOrderHelper
The root value is 4
Traversing down the right node
Entering inOrderHelper with { value: 5 }
Root is not null, so continue
Traversing down the left node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
The root value is 5
Traversing down the right node
Entering inOrderHelper with undefined
Root is null, so back up
Exiting inOrderHelper
Exiting inOrderHelper
Exiting inOrderHelper
You can also use online tools, like BinaryTreeVisualizer, to see this demonstrated with animations.
How does the program know to stop before the tree is finished? It seems to me that it should continue to go to the runner's left node until it is null, at which point it will skip the console.log
Notice that when the function recurses down the left side, when the recursive function returns, control returns to the parent function, which continues on down the right side. When a recursive function returns, it doesn't immediately end the parent function. The parent function treats the recursive function like any other function. It calls it and then, when it returns, goes on to the next thing.
How does the program know that a node has already been printed? It seems to me that it would just print the minimum value repeatedly or once before traversing to the maximum value but apparently the nodes are being checked off somehow.
This is where javascript gets a little bit confusing. Essentially, the function is trying to go down the left and right side, but if the root value is a string, like "B", then root.left and root.right refer to properties that don't exist. In javascript, rather than throwing an error, it just returns undefined. So when we recurse on root.left and that value is undefined then we do nothing.
So, in our example tree:
{
left: {
left: {
value: 1,
},
value: 2,
right: {
value: 3,
},
},
value: 4,
right: {
value: 5,
},
}
Our first root is { left: { ... }, value: 4, right: { value: 5 } }
When we go to the left, root is now { left: { value: 1 }, value: 2, right: { value: 3 } }.
When we go left again, the root is now { value: 1 }.
When we go left again, the root is now undefined, so we do nothing and return to the previous call where the root is { value: 1 }.
We print 1.
Then we go to the right and the root is now undefined, so we do nothing and return to the previous call where the root is { value: 1 }.
We're done with { value: 1 }, so we return to the previous call where the root is { left: { value: 1 }, value: 2, right: { value: 3 } }
We print 2.
Now we go down to the right, and the process repeats as it did for the left, printing 3.
We then go back up to the previous root, { left: { ... }, value: 4, right: { value: 5 } }
We print 4.
The we go to the right and, as with the previous examples, print 5.
We return and, since we've arrived at the original function call, we return and end the program.
The end result is that we printed 1, 2, 3, 4, 5, in that order.
How are all the values printed? For example, if the second smallest value is the right node of the third smallest, value, how is the second smallest value account for?
I'm not sure what you're asking, but it's important to note that this function does not sort the tree. It just reports the values. So if the BST was not constructed properly (e.g. a smaller value is the right of a larger value), then it will print those values out of order as well.
