How does the Inorder-tree-walk algorithm move to a different node after hitting a leaf?

Question

A friend and I did the Inorder-tree-walk with pen and paper. We both can't figure out how the algorithm would move 'up' the tree again upon hitting a leaf:

We are using the algorithm as described by our professor and taken from "Introduction to Algorithms, Third Edition" Chapter 12 page 288:

Inorder-tw(node) 
 if node != nil 
   Inorder-tw(node.left)
   print node.key 
   Inorder-tw(node.right)

• To visualize what we did on paper I wrote each "round" as {1; <key_of_node>}
• To understand our thought process you should read all the {1; ..}'s first, then all the {2; ...}'s and so on
• We are stuck when we hit the node with the key 11 where both; node.left and node.right == nil
• This is exactly the point were we don't understand how the algorithm is able to be called again with a the node of the key 17
• We know that the answer is [11,17,18,31,47,57,69,78,81]

                    47            Inorder-tw(node): {1; 47} {2; 18} {3;17} {3; 11} {5; nil}
                  /   \             if node != nil: {1; T} {2; T} {3; T} {4; T} {5; F} node=nil 11.right
                 /     \                Inorder-tw(node.left): {1; 18} {2;17} {3;11} {4; nil}
                18      78              print node.key {4; 11}
                /\       /\             Inorder-tw(node.right) {4; nil}
               /  \     /  \ 
              17   31  57   81
              /         \
             /           \
            11            69        

The example was take from here Though the examples are nicely visualizing what happens in each step, they don't show us how the input is "changed" in the recursive call upon hitting any leaf. As in my head we are stuck forever at node with the key 11 that returns children of the value == nil.

Writing out the calls as I understand them it would be:

Inorder-tw(47)        Inorder-tw(18)        Inorder-tw(17)        Inorder-tw(11)          Inorder-tw(Nil)
  47 != Nil -> True     18 != Nil -> T        17 != Nil -> T        11 != Nil -> T          Nil != Nil FALSE
  Inorder-tw(47.left)   Inorder-tw(18.left)   Inorder-tw(17.left)   Inorder-tw(11.left)

I can't understand how the algorithm is supposed to print even though the if statement is evaluated as FALSE.

Can anyone explain how the algorithm manages to move back up the tree by changing the input in the recursive call upon hitting a leaf?

Answer 1

To understand what happens "when we hit the node with the key 11", let us isolate the call Inoder-tw(node17), which executes the following.

    if node17 != nil 
       Inorder-tw(node11)  # since node17.left is node11
       print 17            # since node17.key is 17 
       Inorder-tw(nil)     # since node17.right is nil

So, right after the call Inorder-tw(node11), which prints key 11, the algorithm will run print 17.

It is as simple as that.

---

You might be wondering how the algorithm will know to come "back" to the statement print 17 when its reaches the end of execution of Inoder-tw(node11), i.e., when it has found that both node11.left == nil and node11.right == nil.

Well, the call Inorder-tw(node11) is just another statement. The pseudocode specifies that, in the form of simple serial statements, when that statement ends, the next statement should be executed. That is how you should understand the pseudocode/the specification of the algorithm.

---

It is a completely different problem as to how an algorithm/this algorithm can be implemented in a particular language runtime or computation model.

• In most popular language runtimes, such as JavaScript, Python, Java, C/C++, C#, etc, there is a "call stack" that remembers where the algorithm/program is running. That is, what are the calls the lead to the current function/procedure/method call. You should have seen those "call stacks" many times when you encounter a runtime error in various languages.
• The runtime also keep track of which statement is running, what is the next statement and, when there is to a need to jump elsewhere to execute, how to locate and reach "elsewhere".

However, how an algorithm is able to run in each language runtime as it is specified is implementation detail. While it is helpful/important to understand those implementation details (so that you can believe that it is possible to implement an algorithm), you should be able to understand the specification of the algorithm by pseudocode, directly.

Answer 2

The function Inorder-tw calls itself recursively; there are 2 recursive calls, 1 for each child of the node. The computer (or an equivalent manual execution on paper) will use an internal memory stack to remember such recursive calls' sequence along with their arguments (here the node pointer) and the instruction-location to resume to. That is how, when the function returns (upon finding node as null, or having processed the node), the program is able to resume its execution in the "parent" node's call.

In your example, the call with node=(11) will resume when the left-child call returns, and also when the right-child call returns.

Answer 3

It seems like you missed the basic understanding of recursion. That's okay - some teachers don't teach it very well and a lot of students don't get it to "click".

Note: some textbooks might call these "algorithms" or "routines" or "procedures". I don't know what's in that textbook. I'm using the word "function" which is standard in most programming languages.

Do you understand what happens when one function calls another function? Like this (Python language):

def f(x): # this is how you define a function in Python
  print(x+" world")

def g():
  f("hello")
  f("goodbye")

I'm not expecting you to know Python but I hope you can see that when you call g it prints hello world and then prints goodbye world. If you can't see why that is, go back and study functions some more.

---

Now, consider that there's no rule stopping a function from calling itself.

...

That's it. That's what recursion is. Recursion is the fact that a function is allowed to call itself. That's all there is. It's not a special rule!

There are things to keep in mind when writing recursive code - like the "always shrinking" rule - but those answer the question: "How can I use recursion to do something useful?" and they do not answer the question: "What is recursion?" which is what you need to understand first.

---

One thing you do have to worry about is getting a stack overflow error if you have too many nested function calls. But that's not even special to recursion. You could have a million different functions where each function calls the next one, and get a stack overflow error that way instead:

def f0():
    pass # this line does nothing
def f1():
    f0()
def f2():
    f1()
... and so on ...
def f1000000():
    f999999()

def main():
    f1000000() # probably a stack overflow

isn't really much different from:

def f():
    f()

def main():
    f() # definitely a stack overflow

except the second one is much easier to write, and therefore, you can do it accidentally. If you wrote a million functions, then you knew what you were doing - it wasn't a mistake.

---

Back to your code. Your code says: "To print a tree in-order, if the root node isn't nil, then print the left child of the root node in-order, then print the root node, then print the right child of the root node in-order."

If I told you these instructions in English, could you follow them? You could. And so can the computer. It has no problem with these instructions.

However, you might need to use pencil and paper to remember what you're doing, because otherwise it could get confusing. When you have to print the left child of 47, you can write down that you still have to go back and print 47 and then its right child.

The computer also does this. Every time it calls a function, it writes down what to do after that function returns. When the function returns it looks at the last writing, erases it, then goes and does that. So when it calls f("hello") it will write down that after f returns it has to go back to the second line of g() (the one that says f("goodbye")). Then it will go to f("hello"). Once f("hello") finishes it will look at the stack and go back to the second line of g() (the one that says f("goodbye")).

That section of memory is called "the stack". When there are too many nested function calls going, it fills up that section of memory and that's the "stack overflow" error. It's not a certain number of calls, by the way - it depends on how much data the computer has to save for each call.