EasyStackTreeDepth-First SearchBinary Tree

Binary Tree Postorder Traversal

1 approach, code in every language

You are given the root of a binary tree. Return the values of its nodes visited in postorder sequence.

A postorder traversal visits the entire left subtree, then the entire right subtree, and records the current node last. As a result, every node appears only after all of its descendants, and the root is always the final value emitted.

This children-before-parent ordering is exactly what you need when freeing a tree or computing a value for a node that depends on its subtrees.

Example 1

Input: root = [1,null,2,3]

Output: [3,2,1]

The root's right child 2 has left child 3. We emit 3, then 2, and finally the root 1.

Example 2

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

Output: [4,5,2,3,1]

Left subtree of 1 yields 4,5,2 (children before their parent 2), then the right child 3, then the root 1 last.

Constraints

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

Reversed Modified Preorder

Produce a node-right-left order with one stack, then reverse it into postorder.

Loading animation…

Intuition

Postorder (left, right, node) is the exact reverse of a modified preorder that visits node, right, then left. That modified order is easy to generate iteratively with a single stack: pop a node, record it, then push its left child before its right child so the right child is processed first. Collecting values this way gives us node-right-left, and reversing that list at the end produces the desired left-right-node order. This sidesteps the trickier bookkeeping of a direct postorder stack, which must remember whether a node's right subtree has already been handled.

Algorithm walkthrough

1Return an empty list immediately when the root is null.
2Push the root onto a stack and prepare an output list.
3While the stack is not empty, pop a node and append its value; this builds a node-right-left sequence.
4Push the node's left child first, then its right child, so the right child is popped before the left.
5After the loop ends, reverse the output list to turn node-right-left into left-right-node.
6Return the reversed list as the postorder result.

Implementation

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result: List[int] = []
        stack: List[TreeNode] = [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        result.reverse()
        return result

Time

O(n)

Space

O(h)

Each node is pushed and popped once, and the final reversal is linear. The stack depth is bounded by the tree height h; the output list itself uses O(n) space, which is required for the answer.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Fitting Order for a Parts Tree is our own problem on the technique behind Binary Tree Postorder Traversal: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free