CODEWITHSUNDEEP
c++recursiondata-structurestreebinary-tree
Scholar
Scholar

Reputation: 293

How do recursive functions do operations on a binary tree?

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?

Upvotes: 0

Views: 344

Answers (1)

David Schwartz
David Schwartz

Reputation: 182865

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:

  1. We call preorderPrint on the root node.

  2. That outputs the contents of the root node.

  3. It calls preorderPrint on the left node.

  4. This outputs the contents of the left node. It calls preorderPrint twice on NULL, which does nothing, and returns.

  5. The original call to preorderPrint resumes, calling preorderPrint on the right pointer of the root node, which is NULL, and does nothing.

Upvotes: 2

Related Questions