C++ Program to Perform Preorder Recursive Traversal of a Given Binary Tree

«
»

This is a C++ Program for performing recursive PreOrder Traversal of a given Binary Tree.

Problem Description

We will be given a Binary Tree and we have to create a recursive C++ program for PreOrder Traversal of that Tree.

Expected Input and Output

Case 1. Balanced Tree:When we have equal weight on both the sides of root.

advertisement
                    25
                  /    \
                 19     29
                / \     / \
              17  20   27 55

Output: 25 19 17 20 29 27 55

Case 2. Right Skewed Tree:When the nodes at every level have just a right child.

                    1
                     \
                      2
                       \
                        3
                         \
                          4
                           \
                            5

Output: 1 2 3 4 5

advertisement

Case 3. Tree having just one node

              15

Output: 15

advertisement
Problem Solution

In PreOrder Traversal of a Binary Tree, we first print the value of the node, then we traverse the left subtree, and in the end, we traverse the right subtree.

Program/Source Code

Here is source code of the C++ Program for PreOrder Traversal of a Binary Tree. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on windows 10. The program output is also shown below.

  1. /* PreOrder Traversal of a given Tree in C++ */
  2. #include<iostream>
  3. using namespace std;
  4. struct node
  5. {
  6.     int info;
  7.     struct node *left, *right;
  8. };
  9. class Tree
  10. {
  11.     public:
  12.         struct node *root;
  13.         struct node *createnode(int key);
  14.         void PreOrder(struct node *root);
  15.         Tree()
  16.         {
  17.             root = NULL;
  18.         }
  19. };
  20. /* Function to create nodes dynamically */
  21. struct node *Tree :: createnode(int key)
  22. {
  23.     struct node *newnode = new node;
  24.     newnode->info = key;
  25.     newnode->left = NULL;
  26.     newnode->right = NULL;
  27.     return(newnode);
  28. }
  29. /* PreOrder Traversal of a Tree */
  30. void Tree :: PreOrder(struct node *root)
  31. {
  32.      if(root != NULL)
  33.      {
  34.           cout<<root->info<<" ";
  35.           PreOrder(root->left);
  36.           PreOrder(root->right);
  37.      }
  38. }
  39. /*
  40.  * Main Function
  41.  */
  42. int main()
  43. {
  44.     Tree t;
  45.     /* Creating first tree */
  46.     struct node *newnode = t.createnode(25);
  47.     newnode->left = t.createnode(27);
  48.     newnode->right = t.createnode(19);
  49.     newnode->left->left = t.createnode(17);
  50.     newnode->left->right = t.createnode(91);
  51.     newnode->right->left = t.createnode(13);
  52.     newnode->right->right = t.createnode(55);
  53.     /* Sample Tree 1. Balanced Tree
  54.      *               25
  55.      *             /    \
  56.      *           27       19
  57.      *          /  \     /  \
  58.      *         17  91   13  55
  59.      */
  60.     cout<<"PreOrder Traversal of  tree 1 is \n";
  61.     t.PreOrder(newnode);
  62.  
  63.     /* Creating second tree */
  64.     struct node *node = t.createnode(1);
  65.     node->right = t.createnode(2);
  66.     node->right->right = t.createnode(3);
  67.     node->right->right->right = t.createnode(4);
  68.     node->right->right->right->right = t.createnode(5);
  69.     /* Sample Tree 2. Unbalanced Tree
  70.      *                1
  71.      *                 \
  72.      *                  2
  73.      *                   \
  74.      *                    3
  75.      *                     \
  76.      *                      4
  77.      *                       \
  78.      *                        5
  79.      */
  80.     cout<<"\n\nPreOrder Traversal  of tree 2 is\n" ;
  81.     t.PreOrder(node);
  82.  
  83.     /* Creating Tree 3 having just a single node */
  84.     struct node *root = t.createnode(15);
  85.     /* Sample Tree 3. Tree having just one root node.
  86.      *              15
  87.      */
  88.     cout<<"\n\nPreOrder traversal of tree 3 is\n";
  89.     t.PreOrder(root);
  90.     return 0;
  91. }
Program Explanation

1. Check if the current node is empty or null.
2. Print the info part of the current node.
3. Traverse the left subtree by recursively calling the PreOrder function.
4. Traverse the right subtree by recursively calling the PreOrder function.

advertisement
Runtime Test Cases
PreOrder Traversal of  tree 1 is
25 27 17 91 19 13 55
 
PreOrder Traversal  of tree 2 is
1 2 3 4 5
 
PreOrder traversal of tree 3 is
15

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

If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn