Preorder Traversal of a Binary Tree using Recursion in C

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

Here is source code of the C Program to Perform Preorder 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 PreorderRecursive.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.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.