Tracing through a Binary Tree

Question

I have the following Binary tree

    3
   /  \
  5     2
 / \    /
1   4   6

My weekness is recursion, so please bear with me, and I need your help to trace through it to get it right.

I have the following code, and what it does is print the nodes in Post Order. So the answer is 1 4 5 6 2 3

void Postorder(Node root) {

if(root == null){
    return;
}

Postorder(root.left);
Postorder(root.right);
System.out.print(root.data + " ");
}

Lets Trace:

Root = 3 (top node), not null, Root.left(5) - go back up to the function

Root = 5, Not null, Root.left(1) - go back up to the function

Root = 1, Not null, Root.left(null), continue, Root.right(null)

Print 1

now this is where I get confused, Root = 1 at this point, I don't see how I go back up to 5 and then go to the right node in the logic. In addition, when I go back up to 5, where do I check if 1 has been visited ?

I am confused.

Thanks for your help.

Answer 1

Perhaps the picture will help. I find recursion difficult as well, and I've found pictures useful. It might be nice to open the diagram in a separate window and have the explanation on the side.

First of all, recursion uses something called a stack. It's the pile of four rectangles you see in the diagram. For example, there are two empty stacks at the very end. Suppose a function A() calls a function B() before A has terminated. Then what needs to happen is we execute A() partway through, then execute B(), then go back and finish executing A(). But when we go to execute B(), we need to remember where we were in A(). Thus, we need to store the information about A() and B() in individual rectangles in the stack. That way, after we finish executing B(), we know where we left off in A() and can finish the function.

So maybe it will help if we step through the recursion with the diagram of the stack. Also suppose we have this:

public static void main( String[] args ) {
    Postorder(3);
}

1

So initially, main runs and its contents get added to the bottom of the stack, as we see in part 1.

1->2

But when main() calls Postorder(3), it hasn't terminated yet. So, in another stack frame, we add the contents of the Postorder(3) function call. You can see this in part 2. The yellow arrows remember where we left off in each stack frame before we went to execute another function.

2->3

Now, we're executing Postorder(3) and we reach the function call Postorder(5). But Postorder(3) hasn't finished running, so in another stack frame, we have to add the contents of Postorder(5). You can see this in part 3.

3->4

Now we're executing Postorder(5). We reach the function call Postorder(1). But Postorder(5) hasn't finished running, so in another stackframe, we have to add the contents of Postorder(1). For simplicity, since 1 has no subnodes, we'll say that Postorder(1) is equivalent to Print(1). This corresponds to part 4.

4->5

Now, in part 4, Print(1) executes, and Postorder(1) terminates. When Postorder(1) terminates, it can be removed from the stack. Also, since Postorder(1) finished, we can resume executing Postorder(5). The yellow arrow tells us that we left off at line 1 of Postorder(5) before we jumped off to execute another function. Well, we can now move on to line 2 of Postorder(5). This corresponds to part 5.

5->6

Line 2 of Postorder(5) is the command Postorder(4). Since Postorder(5) has not yet finished executing, we must add the contents of Postorder(4) to another stack frame. This corresponds to part 6.

...

It's pretty much the same idea from then on. Let me know if you still want me to step through the remaining 8 parts. It gets a bit tedious afterwards. Hopefully this visual helps.

Answer 2

Right, so when you're at Root 1 (a leaf) it will return to the node that called it (5).

Since at "Root 5", it just finished calling Postorder(root.left); (which just returned from printing 1), the next line will run and call Postorder(root.right); .

This will call root = 4. Not null, root.left(null), continue, root.right(null), continue, now print 4.

Now we jump back to the calling node, root = 5. Now its already called Root.left(1); and Root.right(4);. So now its going to print 5.

It will now return to the calling node - in this case the root of the entire tree, root = 3 and now it will traverse the right side in a similar manner.

Answer 3

The recursion is simple. All you need to do is continuously separate the Binary Search Tree into left and right sub-trees.

You also might want to consider creating getters for your variables to better encapsulate your Node class.

Postorder function

public void Postorder( Node root )
{
    if( root == null )
        return;

    // Output the left tree.
    if( root.left != null )
        Postorder( root.left );

    // Output the current node.
    System.out.print( root.data + " " );

    // Output the right tree.
    if( root.right != null )
        Postorder( root.right );        
}

Answer 4

Understanding and visualizing recursion Maybye this will help you, because your understand recursion wrong. U need to remember ALL function calls.