Recursion causes multiple
different calls of the same function to be placed on a stack frame. Each call to the function relies on the previous call beneath it on the stack frame for input, and returns to the previous call after its finished. In effect, each function call is like a new dependent object.
if your inputs are in the order of 5, 2, 9, 1, 3, 11, then your BSTree will look like this (Sorry for the crude Text-art)
Code:
5
_______/ \_______
2 9
_______/ \_______ \_______
1 3 11 The root node is "5" (Referring to each node by its data contents), So, for an
in-order traversal which outputs the above tree to the console window, the process goes a bit like this. Assuming a new, empty, stack frame:
The first function pushed on to the stack frame is inorder( "5" )
when inorder("5") runs, its first statement calls inorder("5".left) which is inorder("2")
when inorder("2") runs, its first statement calls inorder("2".left) which is inorder("1")
when inorder("1") runs, its first statement calls inorder("1".left) which is inorder(NULL)
the stack frame now looks like
Code:
-top-
inorder(NULL)
inorder("1")
inorder("2")
inorder("5")
-bottom- Note, that at this point
no output has been sent to the console window, all we've done is execute the first statement of each function (Well, actually we've checked to make sure they're not NULL too, but that's a minor detail). Each of which has caused a new function to be added to the stack.
At all times, the active function is the function at the
top of the stack frame
Next, inorder(NULL) returns. This removes it from the stack frame, leaving inorder("1") back at the top. Inorder("1") must take up from where it left off, so the next statement is
Code:
System.out.println("1"); after that, it calls inorder("1".right) which is also inorder(NULL).
Finally, inorder("1") is finished, and can be removed from the stack frame.
the function at the top is now inorder("2"). it has already completed inorder("2".left), so it moves onto the next statement
Code:
System.out.println("2"); Then, it moves on to the next statement, inorder("2".right), which, on our schematic is inorder("3")... Now the stack frame looks like
Code:
-top-
inorder("3")
inorder("2")
inorder("5")
-bottom- and so on, so forth. Just to re-iterate, that the active function is always the one at the top. the ones lower down are 'hanging in wait' from the moment that a new function call is pushed to the top of the stack, until the moment that function call returns.