Tree Traversal Techniques (In-order, Pre-order, Post-order)

Tree Traversal হল একটি গাছের (tree) সমস্ত নোডে পৌঁছানোর এবং তাদের পরিদর্শন করার প্রক্রিয়া। গাছের নোডগুলোতে ট্রাভার্স করার তিনটি প্রধান পদ্ধতি হল In-order, Pre-order, এবং Post-order traversal। প্রতিটি পদ্ধতির মধ্যে একেকটি নোডের পরিদর্শন করার সিকোয়েন্স আলাদা।

এখানে, আমরা এই তিনটি ট্রাভার্সাল পদ্ধতি এবং তাদের Java তে কিভাবে প্রয়োগ করা যায়, তা আলোচনা করব।

1. Tree Traversal Overview

Tree Traversal হল সেই প্রক্রিয়া যার মাধ্যমে আমরা গাছের প্রতিটি নোডে একবার পৌঁছানোর চেষ্টা করি। গাছের প্রতিটি নোডে পরিদর্শন করার জন্য তিনটি সাধারণ কৌশল হলো:

• Pre-order Traversal: প্রথমে রুট (root), তারপর বাম সাবট্রি (left subtree), এবং পরে ডান সাবট্রি (right subtree)।
• In-order Traversal: প্রথমে বাম সাবট্রি (left subtree), তারপর রুট (root), এবং পরে ডান সাবট্রি (right subtree)।
• Post-order Traversal: প্রথমে বাম সাবট্রি (left subtree), তারপর ডান সাবট্রি (right subtree), এবং পরে রুট (root)।

প্রতিটি পদ্ধতিতে রুট নোডের অবস্থান এবং তার চারপাশের নোডগুলোর পরিদর্শন সিকোয়েন্সের মধ্যে পার্থক্য রয়েছে।

2. Pre-order Traversal

Pre-order Traversal এ প্রথমে রুট নোড পরিদর্শন করা হয়, তারপর বাম সাবট্রি এবং শেষে ডান সাবট্রি।

2.1. Pre-order Traversal Example

class TreeNode {
    int data;
    TreeNode left, right;

    // Constructor to create a new node
    public TreeNode(int data) {
        this.data = data;
        left = right = null;
    }
}

public class PreOrderTraversal {
    TreeNode root;

    // Pre-order Traversal: root, left, right
    public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        
        // Visit root
        System.out.print(node.data + " ");
        
        // Visit left subtree
        preOrder(node.left);
        
        // Visit right subtree
        preOrder(node.right);
    }

    public static void main(String[] args) {
        PreOrderTraversal tree = new PreOrderTraversal();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        
        System.out.println("Pre-order Traversal:");
        tree.preOrder(tree.root);
    }
}

ব্যাখ্যা:

• Pre-order Traversal এর মধ্যে প্রথমে রুট নোডে চলে যাওয়া হয়, তারপর বাম সাবট্রি এবং পরিশেষে ডান সাবট্রি পরিদর্শন করা হয়।
• preOrder(node) মেথডটি গাছের প্রতিটি নোডে পৌঁছানোর জন্য রিকার্শন ব্যবহার করছে।

আউটপুট:

Pre-order Traversal:
1 2 4 5 3

3. In-order Traversal

In-order Traversal এ প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপর রুট নোডে পৌঁছানো হয় এবং শেষে ডান সাবট্রি পরিদর্শন করা হয়।

3.1. In-order Traversal Example

public class InOrderTraversal {
    TreeNode root;

    // In-order Traversal: left, root, right
    public void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        
        // Visit left subtree
        inOrder(node.left);
        
        // Visit root
        System.out.print(node.data + " ");
        
        // Visit right subtree
        inOrder(node.right);
    }

    public static void main(String[] args) {
        InOrderTraversal tree = new InOrderTraversal();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        
        System.out.println("In-order Traversal:");
        tree.inOrder(tree.root);
    }
}

ব্যাখ্যা:

• In-order Traversal এ প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপর রুট নোডে চলে আসা হয়, এবং শেষে ডান সাবট্রি পরিদর্শন করা হয়।
• inOrder(node) মেথডটি গাছের প্রতিটি নোডে পৌঁছানোর জন্য রিকার্শন ব্যবহার করছে।

আউটপুট:

In-order Traversal:
4 2 5 1 3

4. Post-order Traversal

Post-order Traversal এ প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপর ডান সাবট্রি পরিদর্শন করা হয় এবং শেষে রুট নোড পরিদর্শন করা হয়।

4.1. Post-order Traversal Example

public class PostOrderTraversal {
    TreeNode root;

    // Post-order Traversal: left, right, root
    public void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        
        // Visit left subtree
        postOrder(node.left);
        
        // Visit right subtree
        postOrder(node.right);
        
        // Visit root
        System.out.print(node.data + " ");
    }

    public static void main(String[] args) {
        PostOrderTraversal tree = new PostOrderTraversal();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        
        System.out.println("Post-order Traversal:");
        tree.postOrder(tree.root);
    }
}

ব্যাখ্যা:

• Post-order Traversal এ প্রথমে বাম সাবট্রি পরিদর্শন করা হয়, তারপর ডান সাবট্রি পরিদর্শন করা হয়, এবং শেষে রুট নোড পরিদর্শন করা হয়।
• postOrder(node) মেথডটি গাছের প্রতিটি নোডে পৌঁছানোর জন্য রিকার্শন ব্যবহার করছে।

আউটপুট:

Post-order Traversal:
4 5 2 3 1

5. Comparison of Tree Traversal Techniques

সারাংশ

Tree Traversal হল গাছের সমস্ত নোড পরিদর্শন করার প্রক্রিয়া। In-order, Pre-order, এবং Post-order হল এর তিনটি প্রধান পদ্ধতি, এবং এগুলির মধ্যে প্রতিটি পদ্ধতি গাছের নোডগুলো পরিদর্শন করার আলাদা সিকোয়েন্স প্রদান করে:

• Pre-order Traversal: Root -> Left -> Right
• In-order Traversal: Left -> Root -> Right
• Post-order Traversal: Left -> Right -> Root

এই তিনটি পদ্ধতির মধ্যে In-order সাধারণত binary search trees (BST) এ ব্যবহার করা হয়, Pre-order গাছের কপি বা এক্সপ্রেশন ট্রি ইভালুয়েশনে ব্যবহৃত হয়, এবং Post-order গাছ মুছে ফেলা বা পোস্টফিক্স এক্সপ্রেশন ইভালুয়েশনে ব্যবহৃত হয়।

এই ট্রাভার্সাল পদ্ধতিগুলি Java তে খুব সহজে বাস্তবায়িত করা যায় এবং গাছের অপারেশনগুলোকে আরও কার্যকরী করে তোলে।