How do recursive functions do operations on a binary tree?

Question

I'm having trouble understanding this concept.

 void preorderPrint( TreeNode *root ) {

    if ( root != NULL ) {  // (Otherwise, there's nothing to print.)
       cout << root->item << " ";      // Print the root item.
       preorderPrint( root->left );    // Print items in left subtree.
       preorderPrint( root->right );   // Print items in right subtree.
    }
 }

How does this print out the nodes in the binary tree? It seems like it just traverses the tree and does not print anything other than the root item.

Furthermore, it seems to me that the recursive functions that work with a binary tree just traverse the tree in a straight line. i.e. root->left just follows the trail going to the left most nodes and ignoring the right nodes in the left subtree. How does this work step by step?

One of the most bizarre properties of recursion is that new programmers suddenly forget all rules they have thus far learned about function calls and the stack, and try to imagine a new set of rules which are invariably more complicated and less intuitive. — paddy

David Schwartz David Schwartz · Accepted Answer · 2014-03-24T03:18:03

You're missing the fact that when one function calls another function and the inner function returns, the other function resumes where it left off.

Consider a tree with a root node and a left node. The following happens:

We call preorderPrint on the root node.
That outputs the contents of the root node.
It calls preorderPrint on the left node.
This outputs the contents of the left node. It calls preorderPrint twice on NULL, which does nothing, and returns.
The original call to preorderPrint resumes, calling preorderPrint on the right pointer of the root node, which is NULL, and does nothing.

How do recursive functions do operations on a binary tree?

1 Answers