Problem Statement:
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]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,6,7,5,2,9,8,3,1]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach
- Use a stack to simulate
recursion. - Traverse left subtree first, pushing
nodesinto the stack. - Peek top node:
- If it has a right child not yet visited, traverse right subtree.
- Else, process the node (postorder:
left → right → root).
- Track the last visited node to avoid revisiting right subtrees.
- Continue until all
nodesare processed.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(h) where: h where, h is the height of the tree.
Dry Run
Input: root = [1, 2, 3, null, 4]
Tree Structure:
1
/ \
2 3
\
4
Initialize:
stack = []
curr = 1
ans = []
lastVisited = null
--- First While Loop (curr || stack not empty) ---
curr = 1 → push to stack → stack = [1]
curr = 2 → push to stack → stack = [1, 2]
curr = null
peek = 2
peek.right = 4 and lastVisited != 4 → move curr = 4
curr = 4 → push to stack → stack = [1, 2, 4]
curr = null
peek = 4
peek.right is null → push 4 to ans → ans = [4]
pop 4 → lastVisited = 4
peek = 2
peek.right = 4 and lastVisited == 4 → push 2 to ans → ans = [4, 2]
pop 2 → lastVisited = 2
peek = 1
peek.right = 3 and lastVisited != 3 → move curr = 3
curr = 3 → push to stack → stack = [1, 3]
curr = null
peek = 3
peek.right is null → push 3 to ans → ans = [4, 2, 3]
pop 3 → lastVisited = 3
peek = 1
peek.right = 3 and lastVisited == 3 → push 1 to ans → ans = [4, 2, 3, 1]
pop 1 → lastVisited = 1
stack is empty and curr is null → traversal complete
Output: Result: [4, 2, 3, 1]
var postorderTraversal = function(root) {
let stack = [];
let curr = root;
let ans = [];
let lastVisited = null;
while(curr || stack.length) {
while(curr) {
stack.push(curr);
curr = curr.left;
}
let peek = stack[stack.length - 1];
if(peek.right && peek.right != lastVisited){
curr = peek.right;
} else {
ans.push(peek.val);
lastVisited = stack.pop();
}
}
return ans;
};
def postorderTraversal(root):
stack = []
curr = root
ans = []
lastVisited = None
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
peek = stack[-1]
if peek.right and peek.right != lastVisited:
curr = peek.right
else:
ans.append(peek.val)
lastVisited = stack.pop()
return ans
public List postorderTraversal(TreeNode root) {
Stack stack = new Stack<>();
TreeNode curr = root;
List ans = new ArrayList<>();
TreeNode lastVisited = null;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
TreeNode peek = stack.peek();
if (peek.right != null && peek.right != lastVisited) {
curr = peek.right;
} else {
ans.add(peek.val);
lastVisited = stack.pop();
}
}
return ans;
}
vector postorderTraversal(TreeNode* root) {
stack stack;
TreeNode* curr = root;
vector ans;
TreeNode* lastVisited = nullptr;
while (curr || !stack.empty()) {
while (curr) {
stack.push(curr);
curr = curr->left;
}
TreeNode* peek = stack.top();
if (peek->right && peek->right != lastVisited) {
curr = peek->right;
} else {
ans.push_back(peek->val);
lastVisited = stack.top();
stack.pop();
}
}
return ans;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 1000
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
typedef struct {
TreeNode* data[MAX];
int top;
} Stack;
void initStack(Stack* s) {
s->top = -1;
}
bool isEmpty(Stack* s) {
return s->top == -1;
}
void push(Stack* s, TreeNode* node) {
if (s->top < MAX - 1) {
s->data[++s->top] = node;
}
}
TreeNode* pop(Stack* s) {
if (!isEmpty(s)) {
return s->data[s->top--];
}
return NULL;
}
TreeNode* peek(Stack* s) {
if (!isEmpty(s)) {
return s->data[s->top];
}
return NULL;
}
void postorderTraversal(TreeNode* root) {
Stack stack;
initStack(&stack);
TreeNode* curr = root;
TreeNode* lastVisited = NULL;
while (curr || !isEmpty(&stack)) {
while (curr) {
push(&stack, curr);
curr = curr->left;
}
TreeNode* peekNode = peek(&stack);
if (peekNode->right && peekNode->right != lastVisited) {
curr = peekNode->right;
} else {
printf("%d ", peekNode->val); // Output the node value
lastVisited = pop(&stack);
}
}
}
public IList PostorderTraversal(TreeNode root) {
Stack stack = new Stack();
TreeNode curr = root;
List ans = new List();
TreeNode lastVisited = null;
while (curr != null || stack.Count > 0) {
while (curr != null) {
stack.Push(curr);
curr = curr.left;
}
TreeNode peek = stack.Peek();
if (peek.right != null && peek.right != lastVisited) {
curr = peek.right;
} else {
ans.Add(peek.val);
lastVisited = stack.Pop();
}
}
return ans;
}
