Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Binary Tree Postorder Traversal solution and explanation

EasyBinary TreeDepth-First SearchStackTree8 min read79.0% acceptanceUpdated 9 Apr 2026
Asked atGoogleAmazonBloombergMicrosoftMeta
Practise Binary Tree Postorder Traversal
16:27
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - PythonNeetCodeIO · 16:27 · 60K viewsWatch on YouTube
9 more videos on this problem
  1. Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - PythonNeetCodeIO · 16:27 · 60K views
  2. LeetCode 145. Binary Tree Postorder Traversal RECURSIVELY - Interview Prep Ep 68Fisher Coder · 7:12 · 5K views
  3. LeetCode 145 Binary Tree Postorder Traversal iterativeleetuition · 10:45 · 3K views
  4. 145. Binary Tree Postorder Traversal - Java SolutionCode with Carter · 7:41 · 667 views
  5. 145. Binary Tree Postorder Traversal || Java || Leetcode || HindiCoding Sphere · 3:52 · 591 views
  6. Leetcode | 145. Binary Tree Postorder Traversal | Easy | Java SolutionDeveloper Docs · 3:46 · 497 views
  7. How To Solve "145 Binary Tree Postorder Traversal" on LeetCode - JavaScriptBecoming A Better Dev (with David) · 4:34 · 274 views
  8. LeetCode - 145. Binary Tree Postorder Traversal | JavaOrkhan Gasanov · 4:48 · 108 views
  9. Binary Tree Postorder Traversal - LeetCode 145 TutorialAlvin The Programmer · 5:43 · 103 views
  10. Leetcode 145. Binary Tree Postorder Traversal - iterative method with stackCode-Yao · 9:18 · 61 views

The problem

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

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 the nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?

Approach overview

Problem Overview: Given the root of a binary tree, return the nodes in postorder traversal. Postorder means visiting the left subtree, then the right subtree, and finally the current node. The challenge is producing this order efficiently using either recursion or an explicit stack.

Approach 1: Recursive Postorder Traversal (O(n) time, O(h) space)

The recursive solution mirrors the definition of postorder traversal. Start a depth‑first search from the root. Recursively process the left child, then recursively process the right child, and finally append the current node's value to the result list. Each node is visited exactly once, so the total time complexity is O(n). The space complexity is O(h), where h is the height of the tree, due to the recursion call stack. This approach is concise and easy to reason about, which makes it a common baseline when working with tree traversal problems and depth-first search patterns.

Approach 2: Iterative Postorder Traversal using Two Stacks (O(n) time, O(n) space)

The iterative method avoids recursion by using explicit stack structures. Push the root into the first stack. Repeatedly pop a node, push it into a second stack, then push its left and right children into the first stack. This process effectively creates a modified preorder traversal (root → right → left). When you pop all nodes from the second stack, the order becomes left → right → root, which is exactly postorder. Every node moves through the stacks once, giving O(n) time complexity. Space complexity becomes O(n) because both stacks may store many nodes.

The key insight behind the two‑stack approach is reversing a traversal order. Preorder normally produces root → left → right. By pushing children in a specific order and reversing the result through another stack, you transform it into postorder. This technique appears frequently in iterative binary tree traversal implementations when recursion is not preferred.

Recommended for interviews: The recursive solution is usually the first answer interviewers expect because it directly follows the DFS definition of postorder traversal and is easy to implement correctly. After presenting it, showing the iterative two‑stack approach demonstrates deeper understanding of stack-based tree traversal and how recursion can be simulated with explicit data structures.

Approach 1: Recursive Postorder Traversal

The simplest way to perform a postorder traversal of a binary tree is recursively. In postorder traversal, you need to traverse the left subtree, then traverse the right subtree, finally visit the root node. This means visiting the left child, then the right child, and then the node itself for each node in the tree.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        self.postorderHelper(root, result)
        return result
    
    def postorderHelper(self, node: TreeNode, result: List[int]):
        if node:
            self.postorderHelper(node.left, result)
            self.postorderHelper(node.right, result)
            result.append(node.val)
import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

    private void postorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        postorderHelper(root.left, result);
        postorderHelper(root.right, result);
        result.add(root.val);
    }
}
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void postorderHelper(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    postorderHelper(root->left, result);
    postorderHelper(root->right, result);
    result.push_back(root->val);
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    postorderHelper(root, result);
    return result;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var postorderTraversal = function(root) {
    const result = [];
    function postorder(node) {
        if (!node) return;
        postorder(node.left);
        postorder(node.right);
        result.push(node.val);
    }
    postorder(root);
    return result;
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void postorderHelper(struct TreeNode* root, int* result, int* returnSize) {
    if (root == NULL) return;
    postorderHelper(root->left, result, returnSize);
    postorderHelper(root->right, result, returnSize);
    result[(*returnSize)++] = root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* result = (int*)malloc(100 * sizeof(int));
    postorderHelper(root, result, returnSize);
    return result;
}
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        PostorderHelper(root, result);
        return result;
    }

    private void PostorderHelper(TreeNode root, List<int> result) {
        if (root == null) return;
        PostorderHelper(root.left, result);
        PostorderHelper(root.right, result);
        result.Add(root.val);
    }
}

The Python solution recursively traverses the binary tree in a postorder style using a helper function, postorderHelper. Once it has traversed both the left and right children nodes, it appends the current node's value to the results list.

Complexity

Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(h), where h is the tree's height, due to recursion call stack.

Try this approach in the editor

Approach 2: Iterative Postorder Traversal using Two Stacks

To perform postorder traversal iteratively, two stacks can be used. The first stack is used to perform a modified preorder traversal (root-right-left), while the second stack reverses this order to provide the postorder traversal (left-right-root). This approach allows the sequence of visiting nodes in postorder traversal without recursion.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack1, stack2 = [root], []
        while stack1:
            node = stack1.pop()
            stack2.append(node)
            if node.left:
                stack1.append(node.left)
            if node.right:
                stack1.append(node.right)
        return [node.val for node in reversed(stack2)]
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);
            if (node.left != null) stack1.push(node.left);
            if (node.right != null) stack1.push(node.right);
        }
        while (!stack2.isEmpty()) {
            TreeNode node = stack2.pop();
            result.add(node.val);
        }
        return result;
    }
}
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    stack<TreeNode*> stack1, stack2;
    stack1.push(root);
    while (!stack1.empty()) {
        TreeNode* node = stack1.top();
        stack1.pop();
        stack2.push(node);
        if (node->left) stack1.push(node->left);
        if (node->right) stack1.push(node->right);
    }
    while (!stack2.empty()) {
        result.push_back(stack2.top()->val);
        stack2.pop();
    }
    return result;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var postorderTraversal = function(root) {
    const res = [];
    if (!root) return res;
    const stack1 = [], stack2 = [];
    stack1.push(root);
    while (stack1.length > 0) {
        const node = stack1.pop();
        stack2.push(node);
        if (node.left) stack1.push(node.left);
        if (node.right) stack1.push(node.right);
    }
    while (stack2.length > 0) {
        res.push(stack2.pop().val);
    }
    return res;
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct Stack {
    struct TreeNode** data;
    int top;
};

struct Stack* createStack(int size) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->data = (struct TreeNode**)malloc(size * sizeof(struct TreeNode*));
    stack->top = -1;
    return stack;
}

void push(struct Stack* stack, struct TreeNode* node) {
    stack->data[++stack->top] = node;
}

struct TreeNode* pop(struct Stack* stack) {
    return stack->data[stack->top--];
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    struct Stack* stack1 = createStack(100);
    struct Stack* stack2 = createStack(100);
    *returnSize = 0;
    if (root == NULL) return NULL;
    push(stack1, root);
    while (!isEmpty(stack1)) {
        struct TreeNode* node = pop(stack1);
        push(stack2, node);
        if (node->left)
            push(stack1, node->left);
        if (node->right)
            push(stack1, node->right);
    }
    int* result = (int*)malloc(100 * sizeof(int));
    while (!isEmpty(stack2)) {
        struct TreeNode* node = pop(stack2);
        result[(*returnSize)++] = node->val;
    }
    return result;
}
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        if (root == null) return result;
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        stack1.Push(root);
        while (stack1.Count > 0) {
            TreeNode node = stack1.Pop();
            stack2.Push(node);
            if (node.left != null) stack1.Push(node.left);
            if (node.right != null) stack1.Push(node.right);
        }
        while (stack2.Count > 0) {
            result.Add(stack2.Pop().val);
        }
        return result;
    }
}

In the Python implementation, we make use of two lists to simulate stacks. The first list ensures we visit nodes in a reverse preorder manner (root-right-left), while the second list reverses this order upon completion to achieve a truly postorder traversal.

Complexity

Time Complexity: O(n)
Space Complexity: O(n) given the storage utilized in maintaining node records in both stacks.

Try this approach in the editor

Approach 3: Recursion

We first recursively traverse the left and right subtrees, then visit the root node.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree. The space complexity mainly depends on the stack space used for recursive calls.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function postorderTraversal(root: TreeNode | null): number[] {
    const ans: number[] = [];
    const dfs = (root: TreeNode | null) => {
        if (!root) {
            return;
        }
        dfs(root.left);
        dfs(root.right);
        ans.push(root.val);
    };
    dfs(root);
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) (ans []int) {
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		dfs(root.Right)
		ans = append(ans, root.Val)
	}
	dfs(root)
	return
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, ans: &mut Vec<i32>) {
        if root.is_none() {
            return;
        }
        let node = root.as_ref().unwrap().borrow();
        Self::dfs(&node.left, ans);
        Self::dfs(&node.right, ans);
        ans.push(node.val);
    }

    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans = vec![];
        Self::dfs(&root, &mut ans);
        ans
    }
}
Try this approach in the editor

Approach 4: Stack Implementation for Postorder Traversal

The order of preorder traversal is: root, left, right. If we change the order of the left and right children, the order becomes: root, right, left. Finally, reversing the result gives us the postorder traversal result.

Therefore, the idea of using a stack to implement non-recursive traversal is as follows:

  1. Define a stack stk, and first push the root node into the stack.
  2. If the stack is not empty, pop a node from the stack each time.
  3. Process the node.
  4. First push the left child of the node into the stack, then push the right child of the node into the stack (if there are child nodes).
  5. Repeat steps 2-4.
  6. Reverse the result to get the postorder traversal result.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree. The space complexity mainly depends on the stack space.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function postorderTraversal(root: TreeNode | null): number[] {
    const ans: number[] = [];
    if (!root) {
        return ans;
    }
    const stk: TreeNode[] = [root];
    while (stk.length) {
        const { left, right, val } = stk.pop();
        ans.push(val);
        left && stk.push(left);
        right && stk.push(right);
    }
    ans.reverse();
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) (ans []int) {
	if root == nil {
		return
	}
	stk := []*TreeNode{root}
	for len(stk) > 0 {
		node := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		ans = append(ans, node.Val)
		if node.Left != nil {
			stk = append(stk, node.Left)
		}
		if node.Right != nil {
			stk = append(stk, node.Right)
		}
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return
}
Try this approach in the editor

Approach 5: Morris Implementation for Postorder Traversal

Morris traversal does not require a stack, and its space complexity is O(1). The core idea is:

Traverse the binary tree nodes,

  1. If the right subtree of the current node root is empty, add the current node value to the result list ans, and update the current node to root.left.
  2. If the right subtree of the current node root is not empty, find the leftmost node next of the right subtree (which is the successor of the root node in inorder traversal):
    • If the left subtree of the successor node next is empty, add the current node value to the result list ans, then point the left subtree of the successor node to the current node root, and update the current node to root.right.
    • If the left subtree of the successor node next is not empty, point the left subtree of the successor node to null (i.e., disconnect next and root), and update the current node to root.left.
  3. Repeat the above steps until the binary tree node is null, and the traversal ends.
  4. Finally, return the reverse of the result list.

The idea of Morris postorder traversal is consistent with Morris preorder traversal, just change the "root-left-right" of preorder to "root-right-left", and finally reverse the result to become "left-right-root".

The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function postorderTraversal(root: TreeNode | null): number[] {
    const ans: number[] = [];
    while (root !== null) {
        const { val, left, right } = root;
        if (right === null) {
            ans.push(val);
            root = left;
        } else {
            let next = right;
            while (next.left !== null && next.left !== root) {
                next = next.left;
            }
            if (next.left === null) {
                ans.push(val);
                next.left = root;
                root = right;
            } else {
                next.left = null;
                root = left;
            }
        }
    }
    return ans.reverse();
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) (ans []int) {
	for root != nil {
		if root.Right == nil {
			ans = append([]int{root.Val}, ans...)
			root = root.Left
		} else {
			next := root.Right
			for next.Left != nil && next.Left != root {
				next = next.Left
			}
			if next.Left == nil {
				ans = append([]int{root.Val}, ans...)
				next.Left = root
				root = root.Right
			} else {
				next.Left = nil
				root = root.Left
			}
		}
	}
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Postorder Traversal

Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(h), where h is the tree's height, due to recursion call stack.

Iterative Postorder Traversal using Two Stacks

Time Complexity: O(n)
Space Complexity: O(n) given the storage utilized in maintaining node records in both stacks.

Recursion–
Stack Implementation for Postorder Traversal–
Morris Implementation for Postorder Traversal–

Complexity analysis

ApproachTimeSpaceWhen to Use
Recursive Postorder TraversalO(n)O(h)Best for clarity and interviews when recursion is acceptable
Iterative Traversal using Two StacksO(n)O(n)When avoiding recursion or demonstrating stack-based traversal logic

Frequently asked questions

Is Binary Tree Postorder Traversal easy or hard?

Binary Tree Postorder Traversal is considered an Easy problem because the recursive solution directly follows the definition of postorder traversal. The iterative stack-based implementation is slightly more involved but still manageable once you understand DFS traversal patterns.

Binary Tree Postorder Traversal Python/Java solution

In Python or Java, the typical solution uses recursion with a helper DFS function. The function recursively processes the left child, then the right child, and appends the current node value to a list. This produces the postorder sequence in O(n) time.

How to solve Binary Tree Postorder Traversal in O(n)?

Perform a depth-first traversal that processes nodes in the order left → right → root. A recursive DFS naturally achieves this in O(n) time. An iterative alternative uses two stacks: push nodes from the first stack into the second while adding children, then pop from the second stack to produce the correct postorder sequence.

What is the best approach for Binary Tree Postorder Traversal?

The recursive depth‑first search approach is the most straightforward solution. Traverse the left subtree, then the right subtree, and finally process the node itself. This visits every node once with O(n) time complexity and O(h) space for the recursion stack, where h is the tree height.

Is Binary Tree Postorder Traversal asked at Google/Amazon/Meta?

Binary tree traversal problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of postorder traversal are commonly used to test understanding of recursion, DFS, and stack-based tree traversal techniques.

What data structure is used in Binary Tree Postorder Traversal?

Traversal relies on recursion or an explicit stack. Recursive solutions use the call stack implicitly during DFS, while iterative approaches use one or two stack data structures to simulate the traversal order.

What is the time complexity of Binary Tree Postorder Traversal?

Binary Tree Postorder Traversal runs in O(n) time because each node in the tree is visited exactly once. Recursive implementations use O(h) auxiliary space from the call stack, while iterative implementations using stacks may use up to O(n) space in the worst case.

Comments

Next problem · similarBinary Tree Inorder TraversalEasy
Now write it yourselfClose this page and solve Binary Tree Postorder Traversal in the editor, without looking.
Practise Binary Tree Postorder Traversal