মডিউল ১৭-৭ঃ Post Order Traversal of Binary Tree

Post-order traversal এর বেলায় প্রথমে left তারপর right তারপর root print করা হয়। অর্থ্যাৎ left->right->root

নিচের উদাহরনে আমরা একটি Binary Tree এর post-order traversal দেখতে পাচ্ছি। এখানে root এ আছে 10, এর left এ 20 এবং right এ 30. এখন এটার যদি post-order traversal করতে হয় তাহলে আমাদের আগে left side এর node গুলো সব print করতে হবে, তারপর right side এর সব print করতে হবে, এবং last এ root print করতে হবে।

Left 20 
(আবার 20 এর নিচে যদি একটি subtree থাকে ঠিক একই rule follow করে  print করতে হবে।)
Right 30 
(আবার 30 এর নিচে যদি একটি subtree থাকে ঠিক একই rule follow করে  print করতে হবে।)
Root 10. 

এবার code এর মাধ্যমে দেখা যাকঃ

এখানে সব সময় left side এ গিয়ে এক এক করে সব node print হবে তারপর right side এর node গুলো print হবে তারপর root print করা হবে।

Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node(int val)
    {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};

// post-order traversal এর function 
void postorder(Node *root)
{
  /* এটি base case অর্থাৎ root এ যদি null পাওয়া যায় তাহলে post-order traversal শেষ হবে */
    if (root == NULL)
    {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    //এখানে root print হবে।
    cout << root->val << " ";
}
int main()
{
    Node *root = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node(30);
    Node *c = new Node(40);
    Node *d = new Node(50);
    Node *e = new Node(60);
    Node *f = new Node(70);
    Node *g = new Node(80);
    Node *h = new Node(90);
    Node *i = new Node(100);

    // connection
    root->left = a;
    root->right = b;
    a->left = c;
    a->right = h;
    c->right = e;
    b->right = d;
    d->left = f;
    d->right = g;
    h->right = i;

    // call
    postorder(root);

    return 0;
}