Algorithm


Tree traversal is a process of visiting and processing each node in a tree data structure. There are three main types of tree traversal: inorder, preorder, and postorder. These terms refer to the order in which the nodes are visited.

  1. Inorder Traversal:

    • In an inorder traversal, the left subtree is visited first, then the root node, and finally the right subtree.
    • The order is Left, Root, Right.

    Example:

    makefile
    Inorder: 4, 2, 5, 1, 3
        1
       / \
      2   3
     / \
    4   5
  • Preorder Traversal:

    • In a preorder traversal, the root node is visited first, followed by the left subtree, and then the right subtree.
    • The order is Root, Left, Right.

    Example:

    makefile
    Preorder: 1, 2, 4, 5, 3
        1
       / \
      2   3
     / \
    4   5
  • Postorder Traversal:

    • In a postorder traversal, the left subtree is visited first, followed by the right subtree, and then the root node.
    • The order is Left, Right, Root.

    Example:

    makefile
    Postorder: 4, 5, 2, 3, 1
        1
       / \
      2   3
     / \
    4   5

These traversals are applicable to various types of trees, including binary trees and binary search trees. They are commonly used in algorithms and data structures for tasks such as searching, insertion, and deletion in trees.

 

Code Examples

#1 Tree Traversal - inorder, preorder and postorder implement in Python

Code - Python Programming

First define a simple binary tree node class:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Now, let's implement the tree traversals:

def inorder_traversal(node):
    """
    Inorder traversal: Left, Root, Right
    """
    if node:
        inorder_traversal(node.left)
        print(node.value, end=" ")
        inorder_traversal(node.right)

def preorder_traversal(node):
    """
    Preorder traversal: Root, Left, Right
    """
    if node:
        print(node.value, end=" ")
        preorder_traversal(node.left)
        preorder_traversal(node.right)

def postorder_traversal(node):
    """
    Postorder traversal: Left, Right, Root
    """
    if node:
        postorder_traversal(node.left)
        postorder_traversal(node.right)
        print(node.value, end=" ")

Now, let's create a sample binary tree and traverse it:

# Sample binary tree
#         1
#        / \
#       2   3
#      / \
#     4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Inorder traversal
print("Inorder Traversal:")
inorder_traversal(root)
print()

# Preorder traversal
print("Preorder Traversal:")
preorder_traversal(root)
print()

# Postorder traversal
print("Postorder Traversal:")
postorder_traversal(root)
Copy The Code & Try With Live Editor

Output

x
+
cmd
Inorder Traversal:
4 2 5 1 3
Preorder Traversal:
1 2 4 5 3
Postorder Traversal:
4 5 2 3 1

#2 Tree Traversal - inorder, preorder and postorder implement in Java

Code - Java Programming

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class TreeTraversal {

    // Inorder traversal: left -> root -> right
    public static void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.data + " ");
            inorderTraversal(root.right);
        }
    }

    // Preorder traversal: root -> left -> right
    public static void preorderTraversal(TreeNode root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
    }

    // Postorder traversal: left -> right -> root
    public static void postorderTraversal(TreeNode root) {
        if (root != null) {
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            System.out.print(root.data + " ");
        }
    }

    public static void main(String[] args) {
        // Create a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // Perform tree traversals
        System.out.println("Inorder traversal:");
        inorderTraversal(root);

        System.out.println("\nPreorder traversal:");
        preorderTraversal(root);

        System.out.println("\nPostorder traversal:");
        postorderTraversal(root);
    }
}
Copy The Code & Try With Live Editor

#3 Tree Traversal - inorder, preorder and postorder implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

// Definition of a binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node with the given data
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function for inorder tree traversal
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// Function for preorder tree traversal
void preorderTraversal(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

// Function for postorder tree traversal
void postorderTraversal(struct Node* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    // Create a sample binary tree
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // Perform different tree traversals
    printf("Inorder Traversal: ");
    inorderTraversal(root);
    printf("\n");

    printf("Preorder Traversal: ");
    preorderTraversal(root);
    printf("\n");

    printf("Postorder Traversal: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
}
Copy The Code & Try With Live Editor

#4 Tree Traversal - inorder, preorder and postorder implement in C++

Code - C++ Programming

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Function to perform inorder traversal
void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        std::cout << root->val << " ";
        inorderTraversal(root->right);
    }
}

// Function to perform preorder traversal
void preorderTraversal(TreeNode* root) {
    if (root) {
        std::cout << root->val << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

// Function to perform postorder traversal
void postorderTraversal(TreeNode* root) {
    if (root) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        std::cout << root->val << " ";
    }
}

int main() {
    // Example usage:
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // Inorder traversal: 4 2 5 1 3
    std::cout << "Inorder traversal: ";
    inorderTraversal(root);
    std::cout << std::endl;

    // Preorder traversal: 1 2 4 5 3
    std::cout << "Preorder traversal: ";
    preorderTraversal(root);
    std::cout << std::endl;

    // Postorder traversal: 4 5 2 3 1
    std::cout << "Postorder traversal: ";
    postorderTraversal(root);
    std::cout << std::endl;

    // Clean up memory (optional)
    // Note: In a real application, you would need to free the allocated memory.
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Tree Traversal - inorder, preorder and postorder-DevsEnv