C++ Program to Print the Nodes at Odd Levels of a Tree

This is a C++ Program to print odd levels of the tree. There are basically two functions in this method. One is to print all nodes at a given level (printGivenLevel), and other is to print level order traversal of the tree (printLevelorder). printLevelorder makes use of printGivenLevel to print nodes at all levels one by one starting from root.

Here is source code of the C++ Program to Print only Odd Numbered Levels of a 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. {
  8.         int data;
  9.         struct node* left;
  10.         struct node* right;
  11. };
  12.  
  13. /*Function protoypes*/
  14. void printGivenLevel(struct node* root, int level);
  15. int height(struct node* node);
  16. struct node* newNode(int data);
  17.  
  18. /* Function to print level order traversal a tree*/
  19. void printLevelOrder(struct node* root)
  20. {
  21.     int h = height(root);
  22.     int i;
  23.     for (i = 1; i <= h; i+=2)
  24.         printGivenLevel(root, i);
  25. }
  26.  
  27. /* Print nodes at a given level */
  28. void printGivenLevel(struct node* root, int level)
  29. {
  30.     if (root == NULL)
  31.         return;
  32.     if (level == 1)
  33.         printf("%d ", root->data);
  34.     else if (level > 1)
  35.     {
  36.         printGivenLevel(root->left, level - 1);
  37.         printGivenLevel(root->right, level - 1);
  38.     }
  39. }
  40.  
  41. /* Compute the "height" of a tree -- the number of
  42.  nodes along the longest path from the root node
  43.  down to the farthest leaf node.*/
  44. int height(struct node* node)
  45. {
  46.     if (node == NULL)
  47.         return 0;
  48.     else
  49.     {
  50.         /* compute the height of each subtree */
  51.         int lheight = height(node->left);
  52.         int rheight = height(node->right);
  53.  
  54.         /* use the larger one */
  55.         if (lheight > rheight)
  56.             return (lheight + 1);
  57.         else
  58.             return (rheight + 1);
  59.     }
  60. }
  61.  
  62. /* Helper function that allocates a new node with the
  63.  given data and NULL left and right pointers. */
  64. struct node* newNode(int data)
  65. {
  66.     struct node* node = (struct node*) malloc(sizeof(struct node));
  67.     node->data = data;
  68.     node->left = NULL;
  69.     node->right = NULL;
  70.  
  71.     return (node);
  72. }
  73.  
  74. /* Driver program to test above functions*/
  75. int main()
  76. {
  77.     struct node *root = newNode(1);
  78.     root->left = newNode(2);
  79.     root->right = newNode(3);
  80.     root->left->left = newNode(4);
  81.     root->left->right = newNode(5);
  82.  
  83.     printf("Level Order traversal of binary tree is \n");
  84.     printLevelOrder(root);
  85.     return 0;
  86. }

Output:

$ g++ OddLevelsOfTree.cpp
$ a.out
 
Level Order traversal of binary tree is 
1 4 5 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

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

If you find any mistake above, kindly email to [email protected]

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.