C++ Program to Implement Double Order Traversal of a Binary Tree

This is a C++ Program to print the double order traversal of the given tree.
Recurse through:
1. Visit root of (sub)tree.
2. Visit left sub-tree.
3. Revisit root of (sub)tree.
4. Visit right sub-tree.

Here is source code of the C++ Program to Implement Double Order Traversal of a Binary Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Perform double-order Recursive Traversal of a Given Binary Tree

```
 */
```
```
# include <iostream>
```
```
# include <cstdlib>
```
```
using namespace std;
```
```
/*
```
```
 * Node Declaration
```
```
 */
```
```
struct node
```
```
{
```
```
        int info;
```
```
        struct node *left;
```
```
        struct node *right;
```
```
}*root;
```
```
/*
```
```
 * Class Declaration
```
```
 */
```
```
class BST
```
```
{
```
```
    public:
```
```
        void insert(node *, node *);
```
```
        void doubleOrder(node *);
```
```
        void display(node *, int);
```
```
        BST()
```
```
        {
```
```
            root = NULL;
```
```
        }
```
```
};
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    int choice, num;
```
```
    BST bst;
```
```
    node *temp;
```
```
    while (1)
```
```
    {
```

        cout << "-----------------" << endl;

        cout << "Operations on BST" << endl;

        cout << "-----------------" << endl;

        cout << "1.Insert Element " << endl;

        cout << "2.Double-Order Traversal" << endl;

```
        cout << "3.Display" << endl;
```
```
        cout << "4.Quit" << endl;
```
```
        cout << "Enter your choice : ";
```
```
        cin >> choice;
```
```
        switch (choice)
```
```
        {
```
```
            case 1:
```
```
                temp = new node;
```

                cout << "Enter the number to be inserted : ";

```
                cin >> temp->info;
```
```
                bst.insert(root, temp);
```
```
                break;
```
```
            case 2:
```

                cout << "Double-Order Traversal of BST:" << endl;

```
                bst.doubleOrder(root);
```
```
                cout << endl;
```
```
                break;
```
```
            case 3:
```

                cout << "Display BST:" << endl;

```
                bst.display(root, 1);
```
```
                cout << endl;
```
```
                break;
```
```
            case 4:
```
```
                exit(1);
```
```
            default:
```

                cout << "Wrong choice" << endl;

```
        }
```
```
    }
```
```
}
```
```
/*
```
```
 * Inserting Element into the Tree
```
```
 */
```

void BST::insert(node *tree, node *newnode)

```
{
```
```
    if (root == NULL)
```
```
    {
```
```
        root = new node;
```
```
        root->info = newnode->info;
```
```
        root->left = NULL;
```
```
        root->right = NULL;
```

        cout << "Root Node is Added" << endl;

```
        return;
```
```
    }
```
```
    if (tree->info == newnode->info)
```
```
    {
```

        cout << "Element already in the tree" << endl;

```
        return;
```
```
    }
```
```
    if (tree->info > newnode->info)
```
```
    {
```
```
        if (tree->left != NULL)
```
```
        {
```

            insert(tree->left, newnode);

```
        }
```
```
        else
```
```
        {
```
```
            tree->left = newnode;
```
```
            (tree->left)->left = NULL;
```
```
            (tree->left)->right = NULL;
```

            cout << "Node Added To Left" << endl;

```
            return;
```
```
        }
```
```
    }
```
```
    else
```
```
    {
```
```
        if (tree->right != NULL)
```
```
        {
```

            insert(tree->right, newnode);

```
        }
```
```
        else
```
```
        {
```
```
            tree->right = newnode;
```
```
            (tree->right)->left = NULL;
```

            (tree->right)->right = NULL;

            cout << "Node Added To Right" << endl;

```
            return;
```
```
        }
```
```
    }
```
```
}
```
```
/*
```
```
 * In Order Traversal
```
```
 */
```
```
void BST::doubleOrder(node *ptr)
```
```
{
```
```
    if (root == NULL)
```
```
    {
```

        cout << "Tree is empty" << endl;

```
        return;
```
```
    }
```
```
    if (ptr != NULL)
```
```
    {
```
```
        cout << ptr->info << "  ";
```
```
        doubleOrder(ptr->left);
```
```
        cout << ptr->info << "  ";
```
```
        doubleOrder(ptr->right);
```
```
    }
```
```
}
```
```
/*
```
```
 * Display Tree Structure
```
```
 */
```
```
void BST::display(node *ptr, int level)
```
```
{
```
```
    int i;
```
```
    if (ptr != NULL)
```
```
    {
```
```
        display(ptr->right, level + 1);
```
```
        cout << endl;
```
```
        if (ptr == root)
```
```
            cout << "Root->:  ";
```
```
        else
```
```
        {
```
```
            for (i = 0; i < level; i++)
```
```
                cout << "       ";
```
```
        }
```
```
        cout << ptr->info;
```
```
        display(ptr->left, level + 1);
```
```
    }
```
```
}
```

Output:

$ g++ DoubleOrrderTraversal.cpp
$ a.out
 
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 12
Root Node is Added
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 11
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 02
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 15
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 19
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 3
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 1
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 70
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 3
Display BST:
 
                            70
                     19
              15
Root->:  12
                     11
              10
                                   4
                            3
                     2
                            1
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 2
Double-Order Traversal of BST:
12  10  2  1  1  2  3  3  4  4  10  11  11  12  15  15  19  19  70  70  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 4
 
------------------
(program exited with code: 0)
Press return to continue

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

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

« Prev - Level Order Traversal of a Tree using Recursion in C++

» Next - Spiral Order Traversal of a Tree using Recursion in C++

Related Posts:

Practice Programming MCQs
Check Computer Science Books
Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Practice Computer Science MCQs

Recommended Articles: