Thread: Please help me to undersatnd recursion in printInorder() function.

Code:

// C program for different tree traversals

Code:

#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
     int data;
     struct node* left;
     struct node* right;
};

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
     struct node* node = (struct node*)
                                  malloc(sizeof(struct node));
     node->data = data;
     node->left = NULL;
     node->right = NULL;

     return(node);
}

/* Given a binary tree, print its nodes according to the
  "bottom-up" postorder traversal. */
void printPostorder(struct node* node)
{
     if (node == NULL)
        return;

     // first recur on left subtree
     printPostorder(node->left);

     // then recur on right subtree
     printPostorder(node->right);

     // now deal with the node
     printf("%d ", node->data);
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
     if (node == NULL)
          return;

     /* first recur on left child */
     printInorder(node->left);

     /* then print the data of node */
     printf("%d ", node->data);  

     /* now recur on right child */
     printInorder(node->right);
}

/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct node* node)
{
     if (node == NULL)
          return;

     /* first print data of node */
     printf("%d ", node->data);  

     /* then recur on left sutree */
     printPreorder(node->left);  

     /* now recur on right subtree */
     printPreorder(node->right);
}    

/* Driver program to test above functions*/
int main()
{
     struct node *root  = newNode(1);
     root->left             = newNode(2);
     root->right           = newNode(3);
     root->left->left     = newNode(4);
     root->left->right   = newNode(5); 

     printf("\nPreorder traversal of binary tree is \n");
     printPreorder(root);

     printf("\nInorder traversal of binary tree is \n");
     printInorder(root);  

     printf("\nPostorder traversal of binary tree is \n");
     printPostorder(root);

     getchar();
     return 0;
}

I think in printInorder() function, this statement

/* first recur on left child */
printInorder(node->left);

will occur again and will not move to printf, could you please tell me how exactly it would work?

Stolen code and can't understand it? Woe for you. The GeeksforGeeks page you stole the code from actually explains it well.

Step through it in a debugger and you wouldn't have to ask silly questions.

Originally Posted by Hobbit

Stolen code and can't understand it? Woe for you. The GeeksforGeeks page you stole the code from actually explains it well.

Step through it in a debugger and you wouldn't have to ask silly questions.

I was just trying to understand the recursion in this code on GeeksforGeeks, was not able to understand, I asked on this forum. What is wrong in it. And I think its no wrong to explore on GeeksforGeeks as this code is opensource. I never said this is my code. If you don't want to answer, please don't and keep your sorrows with you.

I told you what to do. Step through it in a debugger. You can manage that much can't you?

Originally Posted by Salem

You can see recursion in action here as well.

It took me two clicks to get that.

Dear Mr. OP:

People are very sensitive about posting other's code without attribution. Even "open source" code requires attribution. Just remember to do so in the future.

To properly understand recursion it is extremely important to resist the beginner's urge to follow the recursive calls. The entire point of recursion is that you don't need to follow the details. It might be useful to follow the details once or twice just to convince yourself that the mechanism actually works, but after that it's a total waste of time.

Take printInorder, for example:

Code:

void printInorder(struct node *node) {
    if (node == NULL) return;   // if the tree is empty, print nothing
    printInorder(node->left);   // print the left side of the tree in order
    printf("%d ", node->data);  // print the root element
    printInorder(node->right);  // print the right side of the tree in order
}

Clearly, if it does what the comments say then it will print the entire tree in order. And that's that. It is obviously correct and does what we want. The power of recursion comes from the fact that we don't need to follow the recursive calls.