Preorder Traversal of a Binary Tree using Recursion in C++

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.

                    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.

Output: 1 2 3 4 5

Case 3. Tree having just one node

Subscribe Now: C++ Algorithms Newsletter | Important Subjects Newsletters

Output: 15

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.

/* PreOrder Traversal of a given Tree in C++ */

```
#include<iostream>
```
```
using namespace std;
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node *left, *right;
```
```
};
```
```
class Tree
```
```
{
```
```
    public:
```
```
        struct node *root;
```

        struct node *createnode(int key);

        void PreOrder(struct node *root);

```
        Tree()
```
```
        {
```
```
            root = NULL;
```
```
        }
```
```
};
```

/* Function to create nodes dynamically */

struct node *Tree :: createnode(int key)

```
{
```
```
    struct node *newnode = new node;
```
```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
    return(newnode);
```
```
}
```
```
/* PreOrder Traversal of a Tree */
```

void Tree :: PreOrder(struct node *root)

```
{
```
```
     if(root != NULL)
```
```
     {
```
```
          cout<<root->info<<" ";
```
```
          PreOrder(root->left);
```
```
          PreOrder(root->right);
```
```
     }
```
```
}
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
int main()
```
```
{
```
```
    Tree t;
```
```
    /* Creating first tree */
```

    struct node *newnode = t.createnode(25);

```
    newnode->left = t.createnode(27);
```
```
    newnode->right = t.createnode(19);
```

    newnode->left->left = t.createnode(17);

    newnode->left->right = t.createnode(91);

    newnode->right->left = t.createnode(13);

    newnode->right->right = t.createnode(55);

```
    /* Sample Tree 1. Balanced Tree
```
```
     *               25
```
```
     *             /    \
```
```
     *           27       19
```
```
     *          /  \     /  \
```
```
     *         17  91   13  55
```
```
     */
```

    cout<<"PreOrder Traversal of  tree 1 is \n";

```
    t.PreOrder(newnode);
```
```
 
```
```
    /* Creating second tree */
```

    struct node *node = t.createnode(1);

```
    node->right = t.createnode(2);
```

    node->right->right = t.createnode(3);

    node->right->right->right = t.createnode(4);

    node->right->right->right->right = t.createnode(5);

```
    /* Sample Tree 2. Unbalanced Tree
```
```
     *                1
```
```
     *                 \
```
```
     *                  2
```
```
     *                   \
```
```
     *                    3
```
```
     *                     \
```
```
     *                      4
```
```
     *                       \
```
```
     *                        5
```
```
     */
```

    cout<<"\n\nPreOrder Traversal  of tree 2 is\n" ;

```
    t.PreOrder(node);
```
```
 
```

    /* Creating Tree 3 having just a single node */

    struct node *root = t.createnode(15);

    /* Sample Tree 3. Tree having just one root node.

```
     *              15
```
```
     */
```

    cout<<"\n\nPreOrder traversal of tree 3 is\n";

```
    t.PreOrder(root);
```
```
    return 0;
```
```
}
```

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.

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.

« Prev - Inorder Traversal of a Binary Tree using Recursion in C++

» Next - Postorder Traversal of a Binary Tree using Recursion in C++

Related Posts:

Recommended Articles: