Binary Tree: Post-order Traversal

Published in

Data Structure and Algorithms

5 min readJul 5, 2021

Representation

We represent the node as:

Node =>
    Value
    Node Left
    Node Right

Post-order Traversal

The post-order traversal is a kind of depth-first traversal. We perform the following steps:

Recursively traverse the node’s left subtree in post-order
Recursively traverse the node’s right subtree in post-order
Access the node

After traversing the left and the right subtrees of the root node, we consider the traversal complete.

Example

We will do the post-order traversal on the following binary tree:

The nodes in yellow are not yet visited, and the subtrees with dashed edges are also not visited yet. The post-order traversal visits the nodes G, D, H, E, B, F, C, and A.

Let’s take a look at each visit separately. We start with the root node, i.e., node A. By the definition, we first recursively visit both the subtrees first. Therefore, we go past nodes A and B to reach node D. Since node D has no left subtree, we consider the left subtree visited and visit node D’s right subtree. Finally, we reach node G. Since node G has no left and right subtrees, we consider both the subtrees visited and access node G.

We have also visited both the subtrees of node D, so we access node D.

Since we have visited the left subtree of node B, we recursively visit node B’s right subtree and arrive at node E and visit node E’s subtree to arrive at node H.

Since node H has no left and right subtrees, we consider both the subtrees visited and access node H.

We have visited both the subtrees of node E, so we can now access node E.

We have visited both the subtrees of node B, so access node B.

Since we have visited node A’s left subtree, we recursively visit node A’s right subtree and arrive at node C.

Node C has no left subtree, so visit the right subtree and arrive at node F. Since node F has no left and right subtrees, we consider both the subtrees visited and access node F.

We have visited both the subtrees of node C, so we access node C.

Since we have visited both the subtrees of node A, we access node A.

We have visited both the left and right subtrees of the root node. The traversal is complete.

Algorithm

We first visit the left and right subtrees and then access the node.

function postOrder(node) {
    if (node is not present) {
        // Stop here
        return
    }    // Recursively visit the left subtree
    postOrder(node.Left)    // Recursively visit the right subtree
    postOrder(node.Right)    // access the node
    accessNode(node)
}

As the postOrder is a recursive function, we know that each function call is maintained in the call stack using stack frames. When a function returns, the top-most stack frame entry from the call stack is removed because it is the most recent call. Also, the stack has last-in, first-out behavior. Using these two facts, we can translate the recursive version into an iterative version.

The only thing to keep in mind is that we first visit the left subtree, then the right subtree, and finally access the node. So we keep going left until there is no left subtree, then for that node, we traverse the right subtree.

function postOrder() {
    nextNodes = []
    // We explore subtrees of this node
    node = Root
    // We visit each node once
    lastVisited = None    while (nextNodes has nodes OR node is present) {
        // Keep going left
        while (node is present) {
            // We visit this node later
            nextNodes.insertFirst(node)            node = node.Left
        }        // We have visited the left subtree
        // Get the first node from the list
        nodeToAccess = nextNodes.first()        // If there is no right child or the right child
        // is previously visited
        if (nodeToAccess has no right child OR nodeToAccess.Right == lastVisited) {
            // We have visited both the subtrees, so we can
            // remove the node from list
            nextNodes.removeFirst()            // Access the node
            accessNode(nodeToAccess)            // We make sure to visit each node once
            lastVisited = nodeToAccess
        } else {
            // We move to the right, but do not visit the node
            // immediately because we first visit the left subtree
            node = nodeToAccess.Right
        }
    }
}

Complexity Analysis

We maintain some entries in the stack either implicitly or explicitly for both the recursive and iterative versions. As the post-order is a depth-first traversal, we have entries equal to the depth of the current path at any point in time. Also, the maximum depth is the height of the tree. So, the space complexity of the algorithm is O(H), where H is the height of the tree.

Before we talk about time complexity, note that we are doing the following three operations for each of the nodes:

Add node’s left child in the list. It has the worst-case time complexity of O(1).
Add node’s right child in the list. It has the worst-case time complexity of O(1).
Access the node. Assuming we are doing anything complex, the worst-case time complexity for this operation is O(1).

We are doing all the operations on one node in the worst-case O(1), and we have a total of N nodes, so the worst-case time complexity of the post-order traversal is O(N).