Tech Blogs LLD SDE Playbook DSA

Binary Tree Postorder Traversal

Easy Top 250
Associated Patterns
Trees
Interviewed At (Company Tags)
GoogleAmazonMicrosoft
External Reference View on LeetCode

Problem Description

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Examples

Example 1:

Input: root = [1,null,2,3] Output: [3,2,1]

Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [1] Output: [1]

Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Left, Right, Root Traversal Order

Postorder traversal visits a binary tree in the order: Left Subtree -> Right Subtree -> Root Node. We can solve this:

  1. Recursively: Call the helper recursively on the left child, then the right child, and finally record the root node’s value.
  2. Iteratively: Postorder is the reverse of a Root-Right-Left traversal. We can use a stack to run a Root-Right-Left traversal: push root, and while the stack is not empty, pop the top node, record its value to a list, and push its left child first and then its right child. Finally, reverse the list of recorded values to obtain the correct Left-Right-Root postorder sequence.

Solution 1: Recursive Postorder Traversal

Recurse left, then right, and process the parent node value last.

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(root, result);
        return result;
    }

    private void traverse(TreeNode node, List<Integer> list) {
        if (node == null) return;
        traverse(node.left, list);   // left
        traverse(node.right, list);  // right
        list.add(node.val);          // root
    }
}
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        result = []
        
        def traverse(node: Optional[TreeNode]):
            if not node:
                return
            traverse(node.left)    # left
            traverse(node.right)   # right
            result.append(node.val) # root

        traverse(root)
        return result
#include <vector>

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

class Solution {
private:
    void traverse(TreeNode* node, std::vector<int>& list) {
        if (!node) return;
        traverse(node->left, list);
        traverse(node->right, list);
        list.push_back(node->val);
    }

public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> result;
        traverse(root, result);
        return result;
    }
};

Complexity Analysis

  • Time Complexity: O(n) since we visit every node exactly once.
  • Space Complexity: O(h) auxiliary space where h is the tree height, representing the recursion stack depth.

Solution 2: Iterative Traversal via Inverted Root-Right-Left

Run a Root-Right-Left stack traversal and reverse the output to yield Left-Right-Root order.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            result.add(curr.val); // process root (will reverse later)

            // Push left first, so right is popped and processed first
            if (curr.left != null) {
                stack.push(curr.left);
            }
            if (curr.right != null) {
                stack.push(curr.right);
            }
        }
        Collections.reverse(result); // reverse to get Left-Right-Root
        return result;
    }
}
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        result = []
        if not root:
            return result
            
        stack = [root]
        while stack:
            curr = stack.pop()
            result.append(curr.val)
            
            if curr.left:
                stack.append(curr.left)
            if curr.right:
                stack.append(curr.right)
                
        return result[::-1]  # reverse to get Left-Right-Root
#include <vector>
#include <stack>
#include <algorithm>

class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;

        std::stack<TreeNode*> stack;
        stack.push(root);

        while (!stack.empty()) {
            TreeNode* curr = stack.top();
            stack.pop();
            result.push_back(curr->val);

            if (curr->left) {
                stack.push(curr->left);
            }
            if (curr->right) {
                stack.push(curr->right);
            }
        }
        std::reverse(result.begin(), result.end());
        return result;
    }
};

Complexity Analysis

  • Time Complexity: O(n) since we process every node once and reverse the result array in linear time.
  • Space Complexity: O(h) auxiliary space to store nodes in the stack, where h is the tree height.

← All Problems