When you recurse down to the next level, that basically involves taking a snapshot of exactly where you are, then going off to do something else. Once that "something else" is complete, you return to your snapshot and carry on.
It's very similar to calling non-recursive functions. When a function calls xyzzy()
, it knows exactly where to carry on from when the call returns. Recursive functions are identical except that they're all passing through the same pieces of code on the way down and back up.
So, when you come back up a level (having processed the node on the left, for example), you will then print the current node, then go down the right side of the sub-tree.
Consider the sample tree:
2
/ \
1 4
/ \
3 5
\
6
To process this tree, for each node (starting at two), you process the left node, print the current node value, then process the right node.
However, you need to understand that "process the left/right node" is the entire "process left, print current, process right" set of steps over again on one of the children. In this sense, there is no difference between processing the root node and processing any other node.
The "processing" is the printing out, in order, of all nodes under a given point (including that point). It's just a happy effect that if you start at the root node, you get the entire tree :-)
So, in terms of what's actually happening, it's basically following the recursive path:
2, has a left node 1, process it:
| 1, has no left node.
> | 1, print 1.
| 1, has no right node.
| 1, done.
> 2, print 2.
2, has a right node 4, process it.
| 4, has a left node 3, process it.
| | 3, has no left node.
> | | 3, print 3.
| | 3, has no right node.
| | 3, done.
> | 4, print 4.
| 4, has a right node 5, process it.
| | 5, has no left node.
> | | 5, print 5.
| | 5, has a right node 6, process it.
| | | 6, has no left node.
> | | | 6, print 6.
| | | 6, has no right node.
| | | 6, done.
| | 5, done.
| 4, done.
2, done.
If you examine each of the printing lines (see the >
markers), you'll see they come out in the desired order.