# Postorder Traversal of a Binary Tree using Recursion in C

This is a C Program to perform post order traversal. Time Complexity: O(n)

Here is source code of the C Program to Perform Postorder Recursive Traversal of a Given Binary Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include <stdio.h>`
2. `#include <stdlib.h>`
3. ` `
4. `/* A binary tree node has data, pointer to left child`
5. ` and a pointer to right child */`
6. `struct node {`
7. `    int data;`
8. `    struct node* left;`
9. `    struct node* right;`
10. `};`
11. ` `
12. `/* Helper function that allocates a new node with the`
13. ` given data and NULL left and right pointers. */`
14. `struct node* newNode(int data) {`
15. `    struct node* node = (struct node*) malloc(sizeof(struct node));`
16. `    node->data = data;`
17. `    node->left = NULL;`
18. `    node->right = NULL;`
19. ` `
20. `    return (node);`
21. `}`
22. ` `
23. `/* Given a binary tree, print its nodes according to the`
24. ` "bottom-up" postorder traversal. */`
25. `void printPostorder(struct node* node) {`
26. `    if (node == NULL)`
27. `        return;`
28. ` `
29. `    // first recur on left subtree`
30. `    printPostorder(node->left);`
31. ` `
32. `    // then recur on right subtree`
33. `    printPostorder(node->right);`
34. ` `
35. `    // now deal with the node`
36. `    printf("%d ", node->data);`
37. `}`
38. ` `
39. `/* Given a binary tree, print its nodes in inorder*/`
40. `void printInorder(struct node* node) {`
41. `    if (node == NULL)`
42. `        return;`
43. ` `
44. `    /* first recur on left child */`
45. `    printInorder(node->left);`
46. ` `
47. `    /* then print the data of node */`
48. `    printf("%d ", node->data);`
49. ` `
50. `    /* now recur on right child */`
51. `    printInorder(node->right);`
52. `}`
53. ` `
54. `/* Given a binary tree, print its nodes in inorder*/`
55. `void printPreorder(struct node* node) {`
56. `    if (node == NULL)`
57. `        return;`
58. ` `
59. `    /* first print data of node */`
60. `    printf("%d ", node->data);`
61. ` `
62. `    /* then recur on left sutree */`
63. `    printPreorder(node->left);`
64. ` `
65. `    /* now recur on right subtree */`
66. `    printPreorder(node->right);`
67. `}`
68. ` `
69. `/* Driver program to test above functions*/`
70. `int main() {`
71. `    struct node *root = newNode(1);`
72. `    root->left = newNode(2);`
73. `    root->right = newNode(3);`
74. `    root->left->left = newNode(4);`
75. `    root->left->right = newNode(5);`
76. ` `
77. `    printf("\n Preorder traversal of binary tree is \n");`
78. `    printPreorder(root);`
79. ` `
80. `    printf("\n Inorder traversal of binary tree is \n");`
81. `    printInorder(root);`
82. ` `
83. `    printf("\n Postorder traversal of binary tree is \n");`
84. `    printPostorder(root);`
85. ` `
86. `    getchar();`
87. `    return 0;`
88. `}`

Output:

```\$ gcc PostorderRecursive.c
\$ ./a.out

Preorder traversal of binary tree is
1 2 4 5 3
Inorder traversal of binary tree is
4 2 5 1 3
Postorder traversal of binary tree is
4 5 2 3 1```

Sanfoundry Global Education & Learning Series – 1000 C Programs.