Log inSign up
easyleetcodeNot Started

Binary Tree Postorder Traversal

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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

In postorder traversal, nodes are visited in the order: Left -> Right -> Root.

Example 1 · Example 1: Standard Tree:

Input: root = [1, null, 2, 3]
Output: [3, 2, 1]
Explanation: Left subtree is empty. Right subtree at 2 has left child 3 (visited first), then 2, then root 1.

Example 2 · Example 2: Empty Tree:

Input: root = []
Output: []
Explanation: Empty tree.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the bottom-up nature of postorder traversal.
  • Implement the elegant Two-Stack iterative algorithm.
  • Implement the Single-Stack with prev pointer pattern.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Process children before parent node.
  • Bottom-up tree calculation (height, diameter, subtree balance).
  • Postorder traversal.

Algorithmic Decision Tree:

  • Recursive: dfs(node.left), dfs(node.right), visit(node.val).
  • Two Stacks: push root to s1; pop, push to s2, push left to s1, push right to s1. Pop s2 to result.

Connected Patterns:

Binary Tree Preorder TraversalBinary Tree Inorder TraversalMaximum Depth of Binary Tree

1. Recursive DFS Postorder Traversal

Intuition

Recursively visit left subtree, then right subtree, then append node.val to result.

When to apply: Standard implementation.

Algorithm

  1. Step 1: If root is null, return.
  2. Step 2: dfs(root.left).
  3. Step 3: dfs(root.right).
  4. Step 4: Append root.val to result.
  5. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* root, vector<int>& ans) {
10 if (!root) return;
11 dfs(root->left, ans);
12 dfs(root->right, ans);
13 ans.push_back(root->val);
14 }
15 vector<int> postorderTraversal(TreeNode* root) {
16 vector<int> ans;
17 dfs(root, ans);
18 return ans;
19 }
20};
21
22int main() {
23 // Sample driver execution
24 cout << "Execution completed successfully." << endl;
25 return 0;
26}
27

Time & Space Complexity

  • Time complexity: O(n) — Visits each node once in O(n) time.
  • Space complexity: O(h) — Call stack depth O(h).

2. Two-Stack Iterative Traversal

Intuition

Push root to s1. While s1 is not empty: pop node, push to s2. Push node.left to s1, then node.right to s1. Once s1 is empty, pop all elements from s2 to result.

When to apply: Simplest iterative postorder implementation.

Algorithm

  1. Step 1: If root is null, return [].
  2. Step 2: Push root to s1.
  3. Step 3: While s1 is not empty:
  4. - Pop node from s1, push to s2.
  5. - If node.left != null push to s1.
  6. - If node.right != null push to s1.
  7. Step 4: While s2 is not empty: pop and append to result.
  8. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> postorderTraversal(TreeNode* root) {
10 vector<int> ans;
11 if (!root) return ans;
12 stack<TreeNode*> s1, s2;
13 s1.push(root);
14 while (!s1.empty()) {
15 TreeNode* node = s1.top();
16 s1.pop();
17 s2.push(node);
18 if (node->left) s1.push(node->left);
19 if (node->right) s1.push(node->right);
20 }
21 while (!s2.empty()) {
22 ans.push_back(s2.top()->val);
23 s2.pop();
24 }
25 return ans;
26 }
27};
28
29int main() {
30 // Sample driver execution
31 cout << "Execution completed successfully." << endl;
32 return 0;
33}
34

Time & Space Complexity

  • Time complexity: O(n) — All nodes are pushed and popped from both stacks.
  • Space complexity: O(n) — Stack 2 holds all n nodes, taking O(n) space.

3. Single-Stack Traversal with Last-Visited Tracking

Intuition

Keep pointer curr = root and lastVisited = null. Go left as far as possible pushing nodes. Peek at stack top: if top.right exists and top.right != lastVisited, move curr = top.right. Otherwise, pop top, visit top.val, and update lastVisited = top.

When to apply: Memory-optimal iterative solution (O(h) auxiliary space instead of O(n)).

Algorithm

  1. Step 1: curr = root, lastVisited = null, stack = empty.
  2. Step 2: While curr != null or stack is non-empty:
  3. - While curr != null: push curr, curr = curr.left.
  4. - Peek peekNode = stack.top.
  5. - If peekNode.right != null && lastVisited != peekNode.right: curr = peekNode.right.
  6. - Else: add peekNode.val, lastVisited = stack.pop().
  7. Step 3: Return result.

Postorder Trace for root = [1, 2, 3]

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Traverse left from root 1 to node 2
Visual state
Values and pointers at this exact step
tree
Root
1
Left
2
Right
3

Node order shown; add connections to display explicit tree edges.

curr: 2
Check / comparison
Visit left child 2
Decision / next transition
Add 2 to output.
Why this step matters

Step 1: Traverse left from root 1 to node 2. Node 2 has no children, visit 2: [2].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> postorderTraversal(TreeNode* root) {
10 vector<int> ans;
11 stack<TreeNode*> st;
12 TreeNode* curr = root;
13 TreeNode* lastVisited = nullptr;
14 while (curr || !st.empty()) {
15 while (curr) {
16 st.push(curr);
17 curr = curr->left;
18 }
19 TreeNode* peekNode = st.top();
20 if (peekNode->right && lastVisited != peekNode->right) {
21 curr = peekNode->right;
22 } else {
23 ans.push_back(peekNode->val);
24 lastVisited = peekNode;
25 st.pop();
26 }
27 }
28 return ans;
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n) — Every node is visited at most twice.
  • Space complexity: O(h) — Single stack uses O(h) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive DFSO(n)O(h)Natural call stack recursion: left, right, visit.Call stack.
2.Two StacksO(n)O(n)Reversed preorder using second stack.Linear space consumption.
3.Single Stack with Last VisitedOptimalO(n)O(h)Single stack tracking right-child completion.None. Memory optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [] -> returns [].
  • Single node tree: root = [1] -> returns [1].
  • Left-skewed or right-skewed trees.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why postorder is used for tree deletion (children must be freed before parent).
  2. Explain the two-stack trick: standard preorder is Root->Left->Right; changing to Root->Right->Left and reversing yields Left->Right->Root (Postorder!).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is postorder traversal commonly used when deleting a binary tree?

Back to DSA Sheet