Tree Traversal - inorder, preorder and postorder | DSA in C++ - Software Development PDF Download

Introduction

Tree traversal is an essential concept in computer science, particularly in data structures and algorithms. It refers to the process of visiting each node of a tree exactly once. There are three commonly used tree traversal methods: inorder, preorder, and postorder. In this article, we will explore these traversal techniques, understand their implementation in C++, and provide examples to solidify the concepts.

Tree Basics

Before diving into tree traversals, let's quickly review some fundamental concepts related to trees:

• Node: Each element in a tree is called a node. It contains a value and may have child nodes.
• Root: The topmost node of a tree is called the root.
• Child: A node directly connected to another node when moving away from the root.
• Parent: The converse notion of a child.
• Leaf: A node without any children is called a leaf node.

Inorder Traversal

In inorder traversal, the left subtree is visited first, followed by the root node, and then the right subtree. This traversal technique results in nodes being visited in ascending order in case of a binary search tree.

Code Example:

// Node definition for a binary tree

struct Node {

    int data;

    Node* left;

    Node* right;

};

// Inorder traversal function

void inorderTraversal(Node* root) {

    if (root == nullptr) {

        return;

    }

    inorderTraversal(root->left);    // Traverse left subtree

    cout << root->data << " ";       // Visit current node

    inorderTraversal(root->right);   // Traverse right subtree

}

Example Tree:

       4

     /   \

    2     6

   / \   / \

  1   3 5   7

Output:

1 2 3 4 5 6 7

Preorder Traversal

In preorder traversal, the root node is visited first, followed by the left subtree, and then the right subtree.

Code Example:

// Preorder traversal function

void preorderTraversal(Node* root) {

    if (root == nullptr) {

        return;

    }

    cout << root->data << " ";      // Visit current node

    preorderTraversal(root->left);  // Traverse left subtree

    preorderTraversal(root->right); // Traverse right subtree

}

Example Tree:

       4

     /   \

    2     6

   / \   / \

  1   3 5   7

Output:

4 2 1 3 6 5 7

Postorder Traversal

In postorder traversal, the left subtree is visited first, followed by the right subtree, and then the root node.

Code Example:

// Postorder traversal function

void postorderTraversal(Node* root) {

    if (root == nullptr) {

        return;

    }

    postorderTraversal(root->left);   // Traverse left subtree

    postorderTraversal(root->right);  // Traverse right subtree

    cout << root->data << " ";        // Visit current node

}

Example Tree:

       4

     /   \

    2     6

   / \   / \

  1   3 5   7

Output:

1 3 2 5 7 6 4

Sample Problems

Problem 1: Given a binary tree, perform inorder traversal and print the elements.

Input:

       1

     /   \

    2     3

   / \   / \

  4   5 6   7

Output:

4 2 5 1 6 3 7

Solution:

#include <iostream>

using namespace std;

// Node definition for a binary tree

struct Node {

    int data;

    Node* left;

    Node* right;

};

// Inorder traversal function

void inorderTraversal(Node* root) {

    if (root == nullptr) {

        return;

    }

    inorderTraversal(root->left);    // Traverse left subtree

    cout << root->data << " ";       // Visit current node

    inorderTraversal(root->right);   // Traverse right subtree

}

int main() {

    // Create the binary tree

    Node* root = new Node();

    root->data = 1;

        Node* node2 = new Node();

    node2->data = 2;

        Node* node3 = new Node();

    node3->data = 3;

        Node* node4 = new Node();

    node4->data = 4;

        Node* node5 = new Node();

    node5->data = 5;

        Node* node6 = new Node();

    node6->data = 6;

        Node* node7 = new Node();

    node7->data = 7;

        root->left = node2;

    root->right = node3;

        node2->left = node4;

    node2->right = node5;

        node3->left = node6;

    node3->right = node7;

        // Perform inorder traversal

    cout << "Inorder traversal: ";

    inorderTraversal(root);

        return 0;

}

Output:

Inorder traversal: 4 2 5 1 6 3 7

Problem 2: Given a binary tree, perform postorder traversal and calculate the sum of all elements.

Input:

        5

      /   \

     3     8

    / \   / \

   1   2 6   9

Output:

Sum: 34

Solution:

#include <iostream>

using namespace std;

// Node definition for a binary tree

struct Node {

    int data;

    Node* left;

    Node* right;

};

// Postorder traversal function

int postorderTraversal(Node* root) {

    if (root == nullptr) {

        return 0;

    }

    int leftSum = postorderTraversal(root->left);    // Traverse left subtree

    int rightSum = postorderTraversal(root->right);  // Traverse right subtree

    int currentSum = root->data + leftSum + rightSum; // Calculate sum

    return currentSum;

}

int main() {

    // Create the binary tree

    Node* root = new Node();

    root->data = 5;

        Node* node2 = new Node();

    node2->data = 3;

        Node* node3 = new Node();

    node3->data = 8;

        Node* node4 = new Node();

    node4->data = 1;

        Node* node5 = new Node();

    node5->data = 2;

        Node* node6 = new Node();

    node6->data = 6;

        Node* node7 = new Node();

    node7->data = 9;

        root->left = node2;

    root->right = node3;

        node2->left = node4;

    node2->right = node5;

        node3->left = node6;

    node3->right = node7;

        // Perform postorder traversal and calculate sum

    int sum = postorderTraversal(root);

    cout << "Sum: " << sum << endl;

        return 0;

}

Output:

Sum: 34

Conclusion

Tree traversal is a fundamental concept in data structures and algorithms. In this article, we explored three common tree traversal techniques: inorder, preorder, and postorder. We provided clear code examples and explanations for each traversal method in C++. By understanding these traversal techniques, you'll be able to efficiently navigate through tree structures and perform various operations on tree nodes.
Remember to practice implementing and using these traversal methods with different tree structures to solidify your understanding.