Postorder Traversal

Postorder traversal visits the node in the order: Left -> Right -> Root

Algorithm for Postorder Traversal:

Algorithm Postorder(tree)

Traverse the left subtree, i.e., call Postorder(left->subtree)
Traverse the right subtree, i.e., call Postorder(right->subtree)
Visit the root

Uses of Postorder Traversal:

Postorder traversal is used to delete the tree. See the question for the deletion of a tree for details.
Postorder traversal is also useful to get the postfix expression of an expression tree.
Postorder traversal can help in garbage collection algorithms, particularly in systems where manual memory management is used.

Code Snippet for Postorder Traversal:

C++

// Given a binary tree, print its nodes according to the
// "bottom-up" postorder traversal.
void printPostorder(struct Node* node)
{
    if (node == NULL)
        return;

    // First recur on left subtree
    printPostorder(node->left);

    // Then recur on right subtree
    printPostorder(node->right);

    // Now deal with the node
    cout << node->data << " ";
}

// Given a binary tree, print its nodes according to the
// "bottom-up" postorder traversal.
void printPostorder(struct node* node)
{
    if (node == NULL)
        return;

    // First recur on left subtree
    printPostorder(node->left);

    // Then recur on right subtree
    printPostorder(node->right);

    // Now deal with the node
    printf("%d ", node->data);
}

Java

// Given a binary tree, print its nodes according to the
// "bottom-up" postorder traversal.
void printPostorder(Node node)
{
    if (node == null)
        return;

    // First recur on left subtree
    printPostorder(node.left);

    // Then recur on right subtree
    printPostorder(node.right);

    // Now deal with the node
    System.out.print(node.key + " ");
}

Python3

# A function to do postorder tree traversal
def printPostorder(root):

    if root:

        # First recur on left child
        printPostorder(root.left)

        # The recur on right child
        printPostorder(root.right)

        # Now print the data of node
        print(root.val, end=" "),

// Given a binary tree, print its nodes according to
// the "bottom-up" postorder traversal.
void printPostorder(Node node)
{
    if (node == null)
        return;

    // First recur on left subtree
    printPostorder(node.left);

    // Then recur on right subtree
    printPostorder(node.right);

    // Now deal with the node
    Console.Write(node.key + " ");
}

Javascript

// Given a binary tree, print its nodes according 
// to the "bottom-up" postorder traversal
function printPostorder(node) {
    if (node == null)
        return;

    // First recur on left subtree
    printPostorder(node.left);

    // Then recur on right subtree
    printPostorder(node.right);

    // Now deal with the node
    console.log(node.key + " ");
}

Output

Postorder traversal of binary tree is 
4 5 2 3 1

Tree Traversal Techniques – Data Structure and Algorithm Tutorials

Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. In this article, we will discuss about all the tree traversal techniques along with their uses.

Table of Content

Tree Traversal Meaning
Tree Traversal Techniques
Inorder Traversal
Preorder Traversal
Postorder Traversal
Level Order Traversal
Other Tree Traversals
Frequently Asked Questions (FAQs) on Tree Traversal Techniques

Postorder Traversal

Tree Traversal Techniques – Data Structure and Algorithm Tutorials

Similar Reads

Contact Us