Thread: Need help for explanation of the code.

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 inorder*/ 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("\n Preorder traversal of binary tree is \n"); printPreorder(root); printf("\n Inorder traversal of binary tree is \n"); printInorder(root); printf("\n Postorder traversal of binary tree is \n"); printPostorder(root); getchar(); return 0; } The part in which i am stuck in this program is that....say consider in the function printPreorder what happens when when node==NULL.....where does the control flow...all in all if i am able to understand any of the traversal function code be it preorder or any...it could solve my problem.Please help.

Control returns to the calling function, namely main(). The called function ends execution at the return statement.

I apologize for my previous thread i posted on the link:Need help for explanation of the code. ...this new thread contains the same problem which i wrongly posted.

Thank you...but here say i want the preorder traversal....so in the function printPreorder there is a recursion "printPreorder(node->left)" which calls itself....when i took one example of a tree:say- 1 is the root node, 1's left child is 2 and right child is 3, then 2's left child is 4 and right child is 5. First of the all main() called the function printPreorder by passing the pointer to the root. Then as in the function it checked the condition and printed as traversed in preorder...first 1 then 2 then 4 till here i understood but now when it printed 4 after then the statement printPreorder(node->left) will cause the condition node==null to go true...so after then what happens so that the function prints the leftover nodes in the tree of the above example?? Please help.

My answer doesn't really change much... I'll just call your function 'pre' for brevity,

Code:

pre(1)
  pre(1->left)   // in 1, call pre(2)
    pre(2->left) // in 2, call pre(4)
      return       // node == NULL, return to calling function where node was 2
    pre(2->right) // in 2, call pre(5)
      return      //  node == NULL, return to calling fuction where node was 2
    // pre ends execution where node is 2 and return to calling function where node was 1
  pre(1->right)

and so into pre(3).

after then the statement printPreorder(node->left) will cause the condition node==null to go true...so after then what happens so that the function prints the leftover nodes in the tree of the above example?? Please help.

That printPreorder will return to main() just like you wrote. But remember, a recursion function uses the function call stack to repeat itself.

So you made a stack of function calls:
printPostorder(root); /* from main() - 1 */
printPostorder(node->left); /* 2 */
printPostorder(node->left); /* 4 */

The call in the stack that will eventually print 4 calls again to end that side of the tree, and then you have to start on the right side since it is the next recursive call.
printPostorder(node->right); /* right of 4 - null */
printPostorder(node->right); /* right of 2 - node 5 */
printPostorder(node->right); /* right of 1 - node 3 */

That done, you start printing values to unwind the entire stack.
3
5
4
2
1

I'm pretty sure that the order is that...

Anyway, trace the recursion yourself to prove it.

thanks a lot to each one of you.....your support were sufficient to get over the problem..thanks