C++ Program to Implement Preorder Traversal of a Binary Tree

Binary trees are fundamental data structures in computer science, widely used for their efficient data storage and retrieval capabilities. One of the primary operations on binary trees is tree traversal. Traversal refers to the process of visiting each node in the tree exactly once in a specific order. Preorder traversal is one of the depth-first traversal methods where the nodes are recursively visited in this order: root node, left subtree, and then the right subtree. This article will guide you through implementing a C++ program to perform preorder traversal on a binary tree.

Prerequisites

Before diving into the implementation, it’s important to understand the following concepts:

• Binary Tree: A tree data structure where each node has at most two children.
• Preorder Traversal: A type of depth-first traversal where nodes are visited in the order of root, left subtree, and right subtree.
• Tree Traversal: The process of visiting all nodes in a tree in a specific order.
• Recursion: A method where the solution to a problem depends on solutions to smaller instances of the same problem.

Familiarity with C++ programming, including classes and recursion, will be beneficial.

Implementing the Binary Tree

To implement preorder traversal on a binary tree, we will:

1. Define a class for the binary tree node.
2. Implement a function to perform preorder traversal.
3. Create a binary tree and use the function to traverse it.

Pseudocode for Preorder Traversal

1. If the current node is null, return.
2. Visit the current node (print its value).
3. Recursively perform preorder traversal on the left subtree.
4. Recursively perform preorder traversal on the right subtree.

Example

Example 1: Simple Binary Tree

Binary Tree Representation

Consider a simple binary tree:

      1
     / \
    2   3
   / \
  4   5

In preorder traversal, the nodes are visited in the order: 1, 2, 4, 5, 3.

C++ Program

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "Preorder Traversal: ";
    preorderTraversal(root);
    cout << endl;

    return 0;
}

Output

Preorder Traversal: 1 2 4 5 3 

Additional Examples

Example 2: Larger Binary Tree

Binary Tree Representation

Consider a larger binary tree:

         1
       /   \
      2     3
     / \     \
    4   5     6
       / \
      7   8

In preorder traversal, the nodes are visited in the order: 1, 2, 4, 5, 7, 8, 3, 6.

C++ Program

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    root->left->right->left = new Node(7);
    root->left->right->right = new Node(8);

    cout << "Preorder Traversal: ";
    preorderTraversal(root);
    cout << endl;

    return 0;
}

Output

Preorder Traversal: 1 2 4 5 7 8 3 6 

Example 3: Binary Tree with Single Node

Binary Tree Representation

Consider a binary tree with a single node:

  1

In preorder traversal, the node is visited in the order: 1.

C++ Program

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    Node* root = new Node(1);

    cout << "Preorder Traversal: ";
    preorderTraversal(root);
    cout << endl;

    return 0;
}

Output

Preorder Traversal: 1 

Conclusion

Preorder traversal is a fundamental operation for binary trees, essential for various applications such as expression tree evaluation and tree copying