Postorder Traversal

Intuition

Postorder traversal is another method for exploring trees, where we follow the sequence of exploring the left subtree first, then the right subtree, and finally visiting the root node. This approach ensures that we only process the current node after we have fully traversed its left and right subtrees. The order we follow is Left, Right, and then Root.

Approach

In postorder traversal, the method starts by fully exploring the left subtree, followed by the right subtree, and then processing the current node. This traversal method is particularly useful in scenarios where you need to ensure that both child nodes are processed before the parent node. We use a recursive approach to naturally follow this sequence, with each call diving deeper into the left and right children before handling the current node.

Dry Run

Let's break down the steps and the data structures involved:

Step 1: Check if the current node is null. If it is, we've reached the end of a subtree, and the recursive function stops.
Step 2: Recursively traverse the left subtree. This means making a call to the postorder function on the left child of the current node.
Step 3: Recursively traverse the right subtree by calling the postorder function on the right child of the current node.
Step 4: Process the current node by adding its value to the postorder traversal array. This step is done after the left and right subtrees have been fully explored.

This recursive approach uses the call stack to manage the traversal, ensuring that each node is visited in the correct postorder sequence.

#include <bits/stdc++.h>
using namespace std;

// TreeNode structure for the binary tree
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    // Constructor to initialize
    // the TreeNode with a value
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
    
class Solution{
    private:
    // Function to perform postorder
    // traversal recursively
    void recursivePostorder(TreeNode* root, vector<int>& arr){
        // Base case: if root is null, return
        if(root==NULL){
            return;
        }
        // Traverse left subtree
        recursivePostorder(root->left, arr);
        // Traverse right subtree
        recursivePostorder(root->right, arr);
        // Visit the TreeNode
        // (append TreeNode's data to the array)
        arr.push_back(root->data);
    }
    public:
    // Function to get the postorder
    // traversal of a binary tree
    vector<int> postorder(TreeNode* root){
        // Create a vector to
        // store the traversal result
        vector<int> arr;
        // Perform postorder traversal
        // starting from the root
        recursivePostorder(root, arr);
        // Return the postorder
        // traversal result
        return arr;
    }
};

// Function to print the
// elements of a vector
void printVector(const vector<int>& vec) {
    // Iterate through the vector
    // and print each element
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;
}

// Main function
int main()
{
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    Solution sol = Solution();
    // Getting postorder traversal
    vector<int> result = sol.postorder(root);

    // Printing the postorder
    // traversal result
    cout << "Postorder traversal: ";
    printVector(result);

    return 0;
}
import java.util.ArrayList;
import java.util.List;

// TreeNode structure for the binary tree
class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    // Constructor to initialize the TreeNode with a value
    TreeNode(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class Solution {
    // Function to perform postorder traversal recursively
    private void recursivePostorder(TreeNode root, List<Integer> arr) {
        // Base case: if root is null, return
        if (root == null) {
            return;
        }
        // Traverse left subtree
        recursivePostorder(root.left, arr);
        // Traverse right subtree
        recursivePostorder(root.right, arr);
        // Visit the TreeNode (append TreeNode's data to the array)
        arr.add(root.data);
    }

    // Function to get the postorder traversal of a binary tree
    public List<Integer> postorder(TreeNode root) {
        // Create a list to store the traversal result
        List<Integer> arr = new ArrayList<>();
        // Perform postorder traversal starting from the root
        recursivePostorder(root, arr);
        // Return the postorder traversal result
        return arr;
    }
}

// Function to print the elements of a list
public class Main {
    static void printList(List<Integer> list) {
        // Iterate through the list and print each element
        for (int num : list) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Creating a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        Solution sol = new Solution();
        // Getting postorder traversal
        List<Integer> result = sol.postorder(root);

        // Printing the postorder traversal result
        System.out.print("Postorder traversal: ");
        printList(result);
    }
}
class TreeNode:
    def __init__(self, val):
        # Initialize the TreeNode with a value
        self.data = val
        self.left = None
        self.right = None

class Solution:
    def recursive_postorder(self, root, arr):
        # Base case: if root is None, return
        if root is None:
            return
        # Traverse left subtree
        self.recursive_postorder(root.left, arr)
        # Traverse right subtree
        self.recursive_postorder(root.right, arr)
        # Visit the TreeNode (append TreeNode's data to the array)
        arr.append(root.data)

    def postorder(self, root):
        # Create a list to store the traversal result
        arr = []
        # Perform postorder traversal starting from the root
        self.recursive_postorder(root, arr)
        # Return the postorder traversal result
        return arr

# Function to print the elements of a list
def print_list(lst):
    # Iterate through the list and print each element
    print(" ".join(map(str, lst)))

# Main function
if __name__ == "__main__":
    # Creating a sample binary tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    sol = Solution()
    # Getting postorder traversal
    result = sol.postorder(root)

    # Printing the postorder traversal result
    print("Postorder traversal:", end=" ")
    print_list(result)
// TreeNode structure for the binary tree
class TreeNode {
    constructor(val) {
        // Initialize the TreeNode with a value
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    // Function to perform postorder traversal recursively
    recursivePostorder(root, arr) {
        // Base case: if root is null, return
        if (root === null) {
            return;
        }
        // Traverse left subtree
        this.recursivePostorder(root.left, arr);
        // Traverse right subtree
        this.recursivePostorder(root.right, arr);
        // Visit the TreeNode (append TreeNode's data to the array)
        arr.push(root.data);
    }

    // Function to get the postorder traversal of a binary tree
    postorder(root) {
        // Create an array to store the traversal result
        const arr = [];
        // Perform postorder traversal starting from the root
        this.recursivePostorder(root, arr);
        // Return the postorder traversal result
        return arr;
    }
}

// Function to print the elements of an array
function printArray(arr) {
    // Iterate through the array and print each element
    console.log(arr.join(" "));
}

// Main function
function main() {
    // Creating a sample binary tree
    const root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);

    const sol = new Solution();
    // Getting postorder traversal
    const result = sol.postorder(root);

    // Printing the postorder traversal result
    console.log("Postorder traversal:", result.join(" "));
}

// Call main function
main();

Intuition:

The idea behind the iterative approach will be to use a stack to perform postorder traversal to mimick the recursive stack. A recursive approach naturally follows this order by going left, then right, and finally visiting the root when returning from recursion. But in an iterative approach, we don't have the function call stack to track nodes, so we need a way to simulate this order.

A key observation is that if we traverse the tree in Root → Right → Left order (a modified preorder), the result will be a reverse of postorder. This means that if we store nodes in this reversed order and then reverse the list at the end, we get the desired postorder sequence.

Approach:

Push the root node onto the stack to begin traversal.
Process nodes in a modified preorder order (Root → Right → Left) by popping a node, storing its value, and pushing its left and right children onto the stack (right first, then left).
Continue until the stack is empty, ensuring all nodes are processed in this modified order.
Reverse the stored result at the end to transform it into the correct postorder sequence (Left → Right → Root).
Return the final postorder traversal list.

Dry Run:

Solution:

#include<bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};


class Solution{
public:
    // Function to perform postorder traversal on the tree
	vector<int> postorder(TreeNode* root){
        vector<int> result; // to store the result

        stack <TreeNode*> nodeStack; // stack to process the nodes
        nodeStack.push(root); // push the root initially
        
        // Until the stack is empty 
        while(!nodeStack.empty()) {
            TreeNode* node = nodeStack.top(); // get the top node 
            nodeStack.pop(); // pop it from the stack 

            result.push_back(node-> data); // add it to the list
            
            // Add its left child if it exists
            if(node-> left) nodeStack.push(node-> left); 
            
            // Add its right child if it exists
            if(node-> right) nodeStack.push(node-> right);
        }
        
        // Reverse the list to get the postorder traversal
        reverse(result.begin(), result.end());

        return result; // Return the result
	}
};

int main() {
    // Create a simple binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    // Create Solution object and call postorder method
    Solution sol;
    vector<int> result = sol.postorder(root);
    
    // Print the result
    for (int val : result) {
        cout << val << " ";  // Output: 4 5 2 6 3 1
    }
    cout << endl;

    return 0;
}
import java.util.*;

// Definition for a binary tree node.
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    // Function to perform postorder traversal on the tree
    public List<Integer> postorder(TreeNode root) {
        List<Integer> result = new ArrayList<>(); // to store the result

        Stack<TreeNode> nodeStack = new Stack<>(); // stack to process the nodes
        if (root != null) nodeStack.push(root); // push the root initially
        
        // Until the stack is empty 
        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop(); // get the top node 

            result.add(node.data); // add it to the list
            
            // Add its left child if it exists
            if (node.left != null) nodeStack.push(node.left);
            
            // Add its right child if it exists
            if (node.right != null) nodeStack.push(node.right);
        }
        
        // Reverse the list to get the postorder traversal
        Collections.reverse(result);

        return result; // Return the result
    }
}

class Main {
    public static void main(String[] args) {
        // Create a simple binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        // Create Solution object and call postorder method
        Solution sol = new Solution();
        List<Integer> result = sol.postorder(root);
        
        // Print the result
        for (int val : result) {
            System.out.print(val + " ");  // Output: 4 5 2 6 3 1
        }
        System.out.println();
    }
}
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

class Solution:
    # Function to perform postorder traversal on the tree
    def postorder(self, root):
        result = []  # to store the result
        
        nodeStack = []  # stack to process the nodes
        if root:
            nodeStack.append(root)  # push the root initially
        
        # Until the stack is empty 
        while nodeStack:
            node = nodeStack.pop()  # get the top node 
            
            result.append(node.data)  # add it to the list
            
            # Add its left child if it exists
            if node.left:
                nodeStack.append(node.left)
            
            # Add its right child if it exists
            if node.right:
                nodeStack.append(node.right)
        
        # Reverse the list to get the postorder traversal
        result.reverse()

        return result  # Return the result

# Create a simple binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

# Create Solution object and call postorder method
sol = Solution()
result = sol.postorder(root)

# Print the result
print(" ".join(map(str, result)))  # Output: 4 5 2 6 3 1
// Definition for a binary tree node.
class TreeNode {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    // Function to perform postorder traversal on the tree
    postorder(root) {
        let result = []; // to store the result

        let nodeStack = []; // stack to process the nodes
        if (root) nodeStack.push(root); // push the root initially
        
        // Until the stack is empty 
        while (nodeStack.length > 0) {
            let node = nodeStack.pop(); // get the top node 

            result.push(node.data); // add it to the list
            
            // Add its left child if it exists
            if (node.left) nodeStack.push(node.left);
            
            // Add its right child if it exists
            if (node.right) nodeStack.push(node.right);
        }
        
        // Reverse the list to get the postorder traversal
        result.reverse();

        return result; // Return the result
    }
}

// Create a simple binary tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

// Create Solution object and call postorder method
let sol = new Solution();
let result = sol.postorder(root);

// Print the result
console.log(result.join(" "));  // Output: 4 5 2 6 3 1

Complexity Analysis:

Time Complexity: O(N), where N is the number of nodes in the tree. Because traversing each nodes once takes O(N) time.

Space Complexity: O(H), where H is the height of the tree. Due to the stack used to mimick the recursive stack behaviour.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code