LeetCode 145: Binary Tree Postorder Traversal Solution

Master LeetCode problem 145 (Binary Tree Postorder Traversal), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

145. Binary Tree Postorder Traversal

Easy

Stack Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To perform postorder traversal iteratively, we can use a stack to simulate the call stack of recursive function calls. The key idea is to visit the left subtree first, then the right subtree, and finally the root. We need two stacks: one for storing nodes to be processed, and another for storing the final result in reverse order.

Start with an empty stack and push the root node onto it.
While the stack is not empty:
- Pop a node from the stack.
- Add the node's value to the result stack.
- Push the node's left child (if exists) onto the processing stack.
- Push the node's right child (if exists) onto the processing stack.
Once the processing stack is empty, all nodes have been visited, and we can pop values from the result stack to get the postorder traversal.

Time Complexity: O(n) - we visit each node once
Space Complexity: O(n) - in the worst case (skewed tree), the stack can hold all nodes

Solution Code

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack = new Stack<>();
    Stack<Integer> postOrder = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        postOrder.push(curr.val);
        
        if (curr.left != null) {
            stack.push(curr.left);
        }
        if (curr.right != null) {
            stack.push(curr.right);
        }
    }
    
    while (!postOrder.isEmpty()) {
        result.add(postOrder.pop());
    }
    
    return result;
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 145 (Binary Tree Postorder Traversal)?

This page provides optimized solutions for LeetCode problem 145 (Binary Tree Postorder Traversal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 145 (Binary Tree Postorder Traversal)?

The time complexity for LeetCode 145 (Binary Tree Postorder Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 145 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 145 in Java, C++, or Python.

Back to LeetCode Solutions