Loading…

easyTreesFrequently asked

Tree: Postorder Traversal

Q: How do you solve Tree: Postorder Traversal using the Recursive Postorder — Left, Right, Node approach?

When to use it: Start here. Three lines; the visit comes last. Postorder is defined recursively: to traverse a node, fully traverse its left subtree, then its right subtree, then visit the node. **Visit-last is the defining move.** Putting the visit after both recursive calls means a node is only emitted once everything beneath it has been handled. That is the bottom-up direction. **Why bottom-up matters.** Whenever a parent's action depends on its children already being processed, postorder is the order you want. To free a tree's memory you must release the children before the parent, or you'd lose the pointers to them. To evaluate an expression tree you need both operands (the children) before applying the operator (the parent) — that's postfix / reverse Polish notation. Computing a subtree's height or size is the same shape: combine the children's results, then return the node's. **Base case.** A null pointer has nothing to visit, so it returns and the recursion unwinds. **Root is always last.** Because the root's visit happens only after its entire left and right subtrees, the root value is the final element of a postorder sequence — the mirror image of preorder, where the root is first. Time complexity: O(n). Space complexity: O(h).

Q: How do you solve Tree: Postorder Traversal using the Iterative Postorder — Two Stacks (reverse of Node-Right-Left) approach?

When to use it: Offer when recursion is discouraged. Explain the reverse insight — it's the cleanest way to remember it. Iterative postorder is the trickiest of the three because a node must be emitted only after *both* its subtrees, which is awkward to track with a single stack. The cleanest mental model exploits a symmetry. **The reverse insight.** Postorder is Left → Right → Node. Read it backwards and you get Node → Right → Left, which is just preorder with the two children swapped (a mirrored preorder). Mirrored preorder is easy to generate with a single stack. So: generate the Node-Right-Left sequence, then reverse it, and you have postorder. **The two-stack implementation.** Push the root onto `stack1`. While `stack1` is non-empty, pop a node and push it onto `stack2`; then push its **left child first, then its right** onto `stack1`. Because `stack1` is LIFO, the right child pops before the left, so the order nodes land on `stack2` is Node, Right, Left. `stack2` therefore holds the mirrored-preorder sequence with the last-pushed on top. Draining `stack2` reverses that order, yielding Left, Right, Node — exactly postorder. **Why two stacks beats one.** A single-stack postorder needs a 'last visited' pointer to decide whether a node's right subtree has been processed yet — correct but fiddly. The two-stack version trades O(h) space for O(n) space to gain a far simpler, bug-resistant structure, which is usually the right call in an interview unless space is tight. Time complexity: O(n). Space complexity: O(n).

Trees & BST · 39 of 41 · 8 min

Given a pointer to the root of a binary tree, print the postorder traversal of the tree: the values visited in Left-subtree, Right-subtree, Node order, separated by spaces.

In plain English

Produce the sequence of node values in Left → Right → Node order. A node's value is emitted only after both its subtrees are fully processed, so the root is always last in the output.

Examples

Example 1

Input: root = [4,2,5,1,3] (4 has children 2,5; 2 has children 1,3)
Output: 1 3 2 5 4
Note: Left subtree of 4 postorder is 1 3 2, then right subtree 5, then the root 4 last.

Example 2

Input: root = [1,null,2,3] (1 → right 2; 2 → left 3)
Output: 3 2 1
Note: Deepest left child 3, then 2, then root 1 — root is always last.

Example 3

Input: root = [1]
Output: 1
Note: Single node — no subtrees, just the node.

Constraints

1 ≤ number of nodes ≤ 500
1 ≤ node value ≤ 500
The tree is non-empty
Output values are space-separated in postorder sequence

Clarifying questions4First question: Should I print the values or return a list?Explore questions

Q1.Should I print the values or return a list?
HackerRank prints space-separated values; returning a list is cleaner for testing in a general interview. Confirm the expected output form.
Q2.Recursive or iterative?
Recursive is the clean default. The iterative version is trickier than inorder/preorder, so be ready to explain the two-stack or reverse-of-modified-preorder approach.
Q3.Why is postorder used for deletion?
You must free a node's children before the node itself, otherwise you lose the pointers to them. Postorder guarantees children are processed first.
Q4.Is postorder of a BST sorted?
No. Only inorder yields sorted order on a BST.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Postorder = visit the Left subtree, then the Right subtree, then the Node last. Recursively it's three lines: recurse left, recurse right, visit. The cleanest iterative version uses two stacks (or a modified preorder of Node-Right-Left whose result you reverse): push root onto stack1; while it's non-empty pop a node, push it onto stack2, and push its left then right onto stack1; finally drain stack2. Both are O(n) time and O(n) space. Postorder is the order for freeing nodes and evaluating expression trees.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can produce postorder recursively and iteratively, and whether you know it's the children-before-parent order used for deletion and expression evaluation.

Where candidates slip

Visiting the node too early (before both recursions), or botching the iterative version by forgetting to reverse, or pushing left/right in the wrong order into the second stack.

How to stand out

Write the recursion instantly, then derive the two-stack iterative version by noting postorder is the reverse of a Node-Right-Left traversal, and connect it to expression-tree evaluation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Postorder — Left, Right, Node	`O(n)`	`O(h)`	Start here. Three lines; the visit comes last.	Read
2	Iterative Postorder — Two Stacks (reverse of Node-Right-Left)Optimal	`O(n)`	`O(n)`	Offer when recursion is discouraged. Explain the reverse insight — it's the cleanest way to remember it.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

When is the node visited?

How to read it:Postorder visits the node last, after both subtrees — the bottom-up DFS.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Postorder — Left, Right, Node

TimeO(n)SpaceO(h)

Start here. Three lines; the visit comes last.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Postorder means the node is processed after BOTH subtrees. Where does the visit go relative to the two recursive calls?

2Hint 2Explore hint

Base case: a null node produces nothing → return.

3Hint 3Explore hint

For a real node: recurse left, recurse right, then visit. The visit is the very last action.

A · Core idea

Postorder is defined recursively: to traverse a node, fully traverse its left subtree, then its right subtree, then visit the node.

Visit-last is the defining move. Putting the visit after both recursive calls means a node is only emitted once everything beneath it has been handled. That is the bottom-up direction.

Why bottom-up matters. Whenever a parent's action depends on its children already being processed, postorder is the order you want. To free a tree's memory you must release the children before the parent, or you'd lose the pointers to them. To evaluate an expression tree you need both operands (the children) before applying the operator (the parent) — that's postfix / reverse Polish notation. Computing a subtree's height or size is the same shape: combine the children's results, then return the node's.

Base case. A null pointer has nothing to visit, so it returns and the recursion unwinds.

Root is always last. Because the root's visit happens only after its entire left and right subtrees, the root value is the final element of a postorder sequence — the mirror image of preorder, where the root is first.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,5,1,3]

Postorder order on [4,2,5,1,3]

How to read it:Visit order in parentheses: 1,3,2,5 then 4 last (root).

Rendering diagram…

Final result1 3 2 5 4

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the full code

solution.javaJava

Recursive Postorder — Left, Right, Node — reference

4 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
    Node(int data) { this.data = data; }
7
}
8
 
9
public void postorder(Node root) {
10
    if (root == null) return;          // base case: nothing to visit
11
    postorder(root.left);              // 1) left subtree
12
    postorder(root.right);             // 2) right subtree
13
    System.out.print(root.data + " "); // 3) visit the node LAST
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

Postorder = the same three statements as inorder/preorder with the visit moved to the end. It's the bottom-up traversal: children finish, then the parent. Reach for it whenever a node's result is built from its children's results.

ComplexityO(n) time, O(h) space — Each node is visited exactly once with O(1) work → O(n) time. Recursion depth equals tree height h → O(h) space (O(log n) balanced, O(n) skewed).

E · Edge cases and pitfalls6root = [1] — Both children null, visit 1 → '1'.Explore edge cases

Edge cases handled

root = [1]Both children null, visit 1 → '1'.
Left-skewed chain 3→2→1Drill to deepest, then unwind → '1 2 3'.
Right-skewed chain 1→2→3Deepest right child first → '3 2 1'.

Pitfalls

Visiting before the right recursion — that's not postorder.
Forgetting the null base case.
Recursing right before left — swaps subtree order in the output.

03.2

Approach 2 of 2 · Optimal

Iterative Postorder — Two Stacks (reverse of Node-Right-Left)

TimeO(n)SpaceO(n)

Offer when recursion is discouraged. Explain the reverse insight — it's the cleanest way to remember it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Postorder is Left, Right, Node. What familiar traversal is its exact reverse?

2Hint 2Explore hint

Reverse of postorder is Node, Right, Left — a mirrored preorder. So produce that easily, then reverse the result.

3Hint 3Explore hint

Use stack1 to drive a Node-Right-Left visit, pushing each visited node onto stack2. Draining stack2 (LIFO) yields the reversed sequence = postorder.

A · Core idea

Iterative postorder is the trickiest of the three because a node must be emitted only after both its subtrees, which is awkward to track with a single stack. The cleanest mental model exploits a symmetry.

The reverse insight. Postorder is Left → Right → Node. Read it backwards and you get Node → Right → Left, which is just preorder with the two children swapped (a mirrored preorder). Mirrored preorder is easy to generate with a single stack. So: generate the Node-Right-Left sequence, then reverse it, and you have postorder.

The two-stack implementation. Push the root onto stack1. While stack1 is non-empty, pop a node and push it onto stack2; then push its left child first, then its right onto stack1. Because stack1 is LIFO, the right child pops before the left, so the order nodes land on stack2 is Node, Right, Left. stack2 therefore holds the mirrored-preorder sequence with the last-pushed on top. Draining stack2 reverses that order, yielding Left, Right, Node — exactly postorder.

Why two stacks beats one. A single-stack postorder needs a 'last visited' pointer to decide whether a node's right subtree has been processed yet — correct but fiddly. The two-stack version trades O(h) space for O(n) space to gain a far simpler, bug-resistant structure, which is usually the right call in an interview unless space is tight.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,5,1,3]

Two-stack postorder

How to read it:stack1 produces Node-Right-Left; stack2 reverses it into postorder.

Rendering diagram…

Final result1 3 2 5 4

C · Code with teaching comments

solution.javaJava

Iterative Postorder — Two Stacks (reverse of Node-Right-Left) — optimal

4 teaching notes

1
public void postorder(Node root) {
2
    if (root == null) return;
3
    Deque<Node> stack1 = new ArrayDeque<>();
4
    Deque<Node> stack2 = new ArrayDeque<>();
5
    stack1.push(root);
6
    while (!stack1.isEmpty()) {
7
        Node node = stack1.pop();
8
        stack2.push(node);                              // build Node-Right-Left on s2
9
        if (node.left != null) stack1.push(node.left);  // left first...
10
        if (node.right != null) stack1.push(node.right);// ...right popped first
11
    }
12
    while (!stack2.isEmpty()) {                         // drain reverses -> postorder
13
        System.out.print(stack2.pop().data + " ");
14
    }
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Postorder is reverse(Node-Right-Left). Recognizing that a hard traversal is just the reverse of an easy one is a reusable trick — it turns the most error-prone DFS into 'do a mirrored preorder and flip the result'.

ComplexityO(n) time, O(n) space — Each node is pushed and popped on each stack once → O(n) time. Stack2 holds all n nodes before draining → O(n) space (more than the O(h) recursion uses).

E · Edge cases and pitfalls6root = [1] — s1 pops 1 to s2, no children; drain s2 → '1'.Explore edge cases

Edge cases handled

root = [1]s1 pops 1 to s2, no children; drain s2 → '1'.
Left-skewed chain 3→2→1s2 gets 3,2,1; drained reversed → '1 2 3'.
Right-skewed chain 1→2→3s2 gets 1,2,3; drained reversed → '3 2 1'.

Pitfalls

Forgetting to reverse (drain stack2) — leaves you with Node-Right-Left, not postorder.
Pushing right before left into stack1 — yields Node-Left-Right, whose reverse is wrong.
Using a single stack without a 'last visited' pointer — emits nodes before their right subtree.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void postorder(Node root) { if (root == null) return; Deque<Node> stack1 = new ArrayDeque<>(); Deque<Node> stack2 = new ArrayDeque<>(); stack1.push(root);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Visiting too early

Postorder requires both subtrees to finish before the node is emitted. Printing before the right recursion breaks the order.

Explore the code comparison

Don't write this

def postorder(root):
    if root is None:
        return
    postorder(root.left)
    print(root.data, end=' ')   # too early
    postorder(root.right)

Write this instead

def postorder(root):
    if root is None:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.data, end=' ')   # last -> postorder

Forgetting the reverse in the two-stack version

stack2 ends up holding the Node-Right-Left sequence. Printing it in pop order is what reverses it into postorder; printing in push order gives the wrong sequence.

Explore the code comparison

Don't write this

// printed while building, in Node-Right-Left order
while (!stack1.isEmpty()) {
    Node node = stack1.pop();
    System.out.print(node.data + " "); // wrong order
    ...
}

Write this instead

while (!stack1.isEmpty()) { ... stack2.push(node); ... }
while (!stack2.isEmpty()) {
    System.out.print(stack2.pop().data + " "); // reversed = postorder
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Depth-first traversal in Left → Right → Node order

Code pattern to memorize

postorder(node):
    if node is null: return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Rules to remember

1Order is Left, Right, Node — the node is visited last, after both subtrees.
2Postorder processes children before parents, so it's the order to free/delete nodes safely.
3Two-stack iterative trick: it's reverse of a Node-Right-Left traversal (a mirrored preorder).
4Expression trees evaluate in postorder (operands before the operator) — postfix / RPN.
5The base case (null → return) stops recursion at the bottom of each branch.

Use this pattern when

Freeing or deleting a tree (must release children before the parent)
Evaluating an expression tree (operands before operator → postfix)
Any value computed bottom-up: height, size, subtree sums

Choose another pattern when

You need the root first (serialization, cloning) → preorder
You need sorted BST output → inorder
You need level-by-level output → BFS level order

Interview takeaway

Postorder is the 'bottom-up' DFS: both subtrees finish before the node is visited. It's the natural order whenever a parent's work depends on its children being done first — height, deletion, expression evaluation.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPostorder DFS (Left → Right → Node). The bottom-up traversal where children are processed before parents — used for deletion, expression evaluation, and any subtree-aggregate value. The iterative two-stack version exploits that postorder is the reverse of a Node-Right-Left (mirrored preorder) traversal.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Tree: Level Order Traversal

Continue · Next problem

Tree: Preorder Traversal

easyTreesFrequently asked

Tree: Postorder Traversal

Trees & BST · 39 of 41 · 8 min

Given a pointer to the root of a binary tree, print the postorder traversal of the tree: the values visited in Left-subtree, Right-subtree, Node order, separated by spaces.

In plain English

Produce the sequence of node values in Left → Right → Node order. A node's value is emitted only after both its subtrees are fully processed, so the root is always last in the output.

Examples

Example 1

Input: root = [4,2,5,1,3] (4 has children 2,5; 2 has children 1,3)
Output: 1 3 2 5 4
Note: Left subtree of 4 postorder is 1 3 2, then right subtree 5, then the root 4 last.

Example 2

Input: root = [1,null,2,3] (1 → right 2; 2 → left 3)
Output: 3 2 1
Note: Deepest left child 3, then 2, then root 1 — root is always last.

Example 3

Input: root = [1]
Output: 1
Note: Single node — no subtrees, just the node.

Constraints

1 ≤ number of nodes ≤ 500
1 ≤ node value ≤ 500
The tree is non-empty
Output values are space-separated in postorder sequence

Clarifying questions4First question: Should I print the values or return a list?Explore questions

Q1.Should I print the values or return a list?
HackerRank prints space-separated values; returning a list is cleaner for testing in a general interview. Confirm the expected output form.
Q2.Recursive or iterative?
Recursive is the clean default. The iterative version is trickier than inorder/preorder, so be ready to explain the two-stack or reverse-of-modified-preorder approach.
Q3.Why is postorder used for deletion?
You must free a node's children before the node itself, otherwise you lose the pointers to them. Postorder guarantees children are processed first.
Q4.Is postorder of a BST sorted?
No. Only inorder yields sorted order on a BST.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can produce postorder recursively and iteratively, and whether you know it's the children-before-parent order used for deletion and expression evaluation.

Where candidates slip

Visiting the node too early (before both recursions), or botching the iterative version by forgetting to reverse, or pushing left/right in the wrong order into the second stack.

How to stand out

Write the recursion instantly, then derive the two-stack iterative version by noting postorder is the reverse of a Node-Right-Left traversal, and connect it to expression-tree evaluation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Postorder — Left, Right, Node	`O(n)`	`O(h)`	Start here. Three lines; the visit comes last.	Read
2	Iterative Postorder — Two Stacks (reverse of Node-Right-Left)Optimal	`O(n)`	`O(n)`	Offer when recursion is discouraged. Explain the reverse insight — it's the cleanest way to remember it.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

When is the node visited?

How to read it:Postorder visits the node last, after both subtrees — the bottom-up DFS.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Postorder — Left, Right, Node

TimeO(n)SpaceO(h)

Start here. Three lines; the visit comes last.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Postorder means the node is processed after BOTH subtrees. Where does the visit go relative to the two recursive calls?

2Hint 2Explore hint

Base case: a null node produces nothing → return.

3Hint 3Explore hint

For a real node: recurse left, recurse right, then visit. The visit is the very last action.

A · Core idea

Postorder is defined recursively: to traverse a node, fully traverse its left subtree, then its right subtree, then visit the node.

Visit-last is the defining move. Putting the visit after both recursive calls means a node is only emitted once everything beneath it has been handled. That is the bottom-up direction.

Base case. A null pointer has nothing to visit, so it returns and the recursion unwinds.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,5,1,3]

Postorder order on [4,2,5,1,3]

How to read it:Visit order in parentheses: 1,3,2,5 then 4 last (root).

Rendering diagram…

Final result1 3 2 5 4

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the full code

solution.javaJava

Recursive Postorder — Left, Right, Node — reference

4 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
    Node(int data) { this.data = data; }
7
}
8
 
9
public void postorder(Node root) {
10
    if (root == null) return;          // base case: nothing to visit
11
    postorder(root.left);              // 1) left subtree
12
    postorder(root.right);             // 2) right subtree
13
    System.out.print(root.data + " "); // 3) visit the node LAST
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(h) space — Each node is visited exactly once with O(1) work → O(n) time. Recursion depth equals tree height h → O(h) space (O(log n) balanced, O(n) skewed).

E · Edge cases and pitfalls6root = [1] — Both children null, visit 1 → '1'.Explore edge cases

Edge cases handled

root = [1]Both children null, visit 1 → '1'.
Left-skewed chain 3→2→1Drill to deepest, then unwind → '1 2 3'.
Right-skewed chain 1→2→3Deepest right child first → '3 2 1'.

Pitfalls

Visiting before the right recursion — that's not postorder.
Forgetting the null base case.
Recursing right before left — swaps subtree order in the output.

03.2

Approach 2 of 2 · Optimal

Iterative Postorder — Two Stacks (reverse of Node-Right-Left)

TimeO(n)SpaceO(n)

Offer when recursion is discouraged. Explain the reverse insight — it's the cleanest way to remember it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Postorder is Left, Right, Node. What familiar traversal is its exact reverse?

2Hint 2Explore hint

Reverse of postorder is Node, Right, Left — a mirrored preorder. So produce that easily, then reverse the result.

3Hint 3Explore hint

Use stack1 to drive a Node-Right-Left visit, pushing each visited node onto stack2. Draining stack2 (LIFO) yields the reversed sequence = postorder.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [4,2,5,1,3]

Two-stack postorder

How to read it:stack1 produces Node-Right-Left; stack2 reverses it into postorder.

Rendering diagram…

Final result1 3 2 5 4

C · Code with teaching comments

solution.javaJava

Iterative Postorder — Two Stacks (reverse of Node-Right-Left) — optimal

4 teaching notes

1
public void postorder(Node root) {
2
    if (root == null) return;
3
    Deque<Node> stack1 = new ArrayDeque<>();
4
    Deque<Node> stack2 = new ArrayDeque<>();
5
    stack1.push(root);
6
    while (!stack1.isEmpty()) {
7
        Node node = stack1.pop();
8
        stack2.push(node);                              // build Node-Right-Left on s2
9
        if (node.left != null) stack1.push(node.left);  // left first...
10
        if (node.right != null) stack1.push(node.right);// ...right popped first
11
    }
12
    while (!stack2.isEmpty()) {                         // drain reverses -> postorder
13
        System.out.print(stack2.pop().data + " ");
14
    }
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Each node is pushed and popped on each stack once → O(n) time. Stack2 holds all n nodes before draining → O(n) space (more than the O(h) recursion uses).

E · Edge cases and pitfalls6root = [1] — s1 pops 1 to s2, no children; drain s2 → '1'.Explore edge cases

Edge cases handled

root = [1]s1 pops 1 to s2, no children; drain s2 → '1'.
Left-skewed chain 3→2→1s2 gets 3,2,1; drained reversed → '1 2 3'.
Right-skewed chain 1→2→3s2 gets 1,2,3; drained reversed → '3 2 1'.

Pitfalls

Forgetting to reverse (drain stack2) — leaves you with Node-Right-Left, not postorder.
Pushing right before left into stack1 — yields Node-Left-Right, whose reverse is wrong.
Using a single stack without a 'last visited' pointer — emits nodes before their right subtree.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Visiting too early

Postorder requires both subtrees to finish before the node is emitted. Printing before the right recursion breaks the order.

Explore the code comparison

Don't write this

def postorder(root):
    if root is None:
        return
    postorder(root.left)
    print(root.data, end=' ')   # too early
    postorder(root.right)

Write this instead

def postorder(root):
    if root is None:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.data, end=' ')   # last -> postorder

Forgetting the reverse in the two-stack version

stack2 ends up holding the Node-Right-Left sequence. Printing it in pop order is what reverses it into postorder; printing in push order gives the wrong sequence.

Explore the code comparison

Don't write this

// printed while building, in Node-Right-Left order
while (!stack1.isEmpty()) {
    Node node = stack1.pop();
    System.out.print(node.data + " "); // wrong order
    ...
}

Write this instead

while (!stack1.isEmpty()) { ... stack2.push(node); ... }
while (!stack2.isEmpty()) {
    System.out.print(stack2.pop().data + " "); // reversed = postorder
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Depth-first traversal in Left → Right → Node order

Code pattern to memorize

postorder(node):
    if node is null: return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Rules to remember

1Order is Left, Right, Node — the node is visited last, after both subtrees.
2Postorder processes children before parents, so it's the order to free/delete nodes safely.
3Two-stack iterative trick: it's reverse of a Node-Right-Left traversal (a mirrored preorder).
4Expression trees evaluate in postorder (operands before the operator) — postfix / RPN.
5The base case (null → return) stops recursion at the bottom of each branch.

Use this pattern when

Freeing or deleting a tree (must release children before the parent)
Evaluating an expression tree (operands before operator → postfix)
Any value computed bottom-up: height, size, subtree sums

Choose another pattern when

You need the root first (serialization, cloning) → preorder
You need sorted BST output → inorder
You need level-by-level output → BFS level order

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Tree: Level Order Traversal

Continue · Next problem

Tree: Preorder Traversal