Post-Order Traversal

Introduction

Post-Order 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

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

How Post-Order Traversal Works?

Traverse Left Subtree

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

Traverse Right Subtree

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

Visit Root

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

Visualization of Post-Order Traversal

Implementation of Post-Order 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);

// post-order traversal
postOrder(root);
}

# postOrder.py
class Node:
 def __init__(self, data):
     self.data = data
     self.left = None
     self.right = None
def build_tree():
 print("Enter The data: ")
 data = int(input())
 if data == -1:
     return None
 root = Node(data)
 print("Enter data for left: ")
 root.left = build_tree()
 print("Enter data for right: ")
 root.right = build_tree()
 return root
def post_order(root):

 if root is None:
     return
 post_order(root.left)
 post_order(root.right)
 print(root.data, end=" ")
 if __name__ == "__main__":
     # creating tree
     root = build_tree()

     # post-order traversal
     post_order(root)

// postOrder.js
class Node {
 constructor(data) {
     this.data = data;
     this.left = null;
     this.right = null;
 }
}
function buildTree() {
 const data = parseInt(prompt("Enter The data: "));
 if (data === -1) {
     return null;
 }
 const root = new Node(data);
 root.left = buildTree();
 root.right = buildTree();
 return root;
}
function postOrder(root) {
 if (root === null) {
     return;
 }
 postOrder(root.left);
 postOrder(root.right);
 console.log(root.data);
}
if (typeof window !== 'undefined') {
 // creating tree
 const root = buildTree();

 // post-order traversal
 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.

Post-Order Traversal

On this page