Postorder Traversal

A Depth-First Search Method for Visiting Children Before Root in Trees

Introduction

Postorder Traversal visits the left subtree, then the right subtree, and processes the root last. It's useful for operations like deleting nodes or evaluating expression tree

Preorder Traversal visits the node in the order: left->right->root

How Postorder Traversal Works?

1

Traverse Left Subtree

  • The left subtree is visited first (left → right → root).
2

Traverse Right Subtree

  • After the left subtree, the right subtree is recursively traversed.
3

Visit Root

  • Finally, the root node is visited after both the left and right subtrees have been processed.

Implementation of Postorder Traversal

//postorder.cpp
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int data)
{
    this->data = data;
    this->left = NULL;
    this->right = NULL;
}
};
Node *buildTree(Node *root)
{
cout << "Enter The data: " << endl;
int data;
cin >> data;
root = new Node(data);
if (data == -1)
{
    return NULL;
}
cout << "Enter data for left : " << endl;
root->left = buildTree(root->left);
cout << "Enter data for right: " << endl;
root->right = buildTree(root->right);
return root;
}
void postorder(Node *root)
{
if (!root)
    return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
int main()
{
// creating tree
Node *root = NULL;
root = buildTree(root);

// postorder order
postorder(root);
}

Time Complexity

Time Complexity: O(n)

  • The function visits each node in the tree exactly once. Given that there are n nodes, the function performs n operations, resulting in O(n) time complexity.

Space Complexity

Space Complexity:O(h),where h is the height of the tree.