Binary Tree Postorder Traversal

Easy
1861.

Binary Tree Postorder Traversal

Binary Tree Postorder Traversal is an easy coding problem on depth-first search, trees and stack, asked in Amazon, Google and Microsoft interviews.

Given the root of a binary tree, return the values of its nodes in postorder: for every node, first everything in its left subtree, then everything in its right subtree, and the node itself last.

Example 1

Input
root = [1,null,2,3]
Output
[3,2,1]
Explanation
3 is the deepest node and comes first; the root 1 is always last.

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]

Example 3

Input
root = [5]
Output
[5]

Constraints

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

Follow-up: The recursive walk is short — can you do it iteratively?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Postorder Traversal — Problem & Solution

Binary Tree Postorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Binary Tree Postorder Traversal is an easy coding problem on depth-first search, trees and stack, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given the root of a binary tree, return the values of its nodes in postorder: for every node, first everything in its left subtree, then everything in its right subtree, and the node itself last.

Example 1

Input: root = [1,null,2,3]
Output: [3,2,1]
Explanation: 3 is the deepest node and comes first; the root 1 is always last.

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]

Example 3

Input: root = [5]
Output: [5]

Constraints

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

Follow-up: The recursive walk is short — can you do it iteratively?

Hints for Binary Tree Postorder Traversal

  1. Hint 1

    In postorder a node is recorded only after both of its subtrees are finished — the root is always last.

  2. Hint 2

    A recursive helper that recurses left, recurses right and then appends the node follows the rule directly.

  3. Hint 3

    For an iterative version: a modified preorder (node, right, left) produces exactly the reverse of postorder.

How to solve Binary Tree Postorder Traversal

Postorder is left subtree, right subtree, then the node. A depth-first helper that appends a node after both of its recursive calls return writes the values in exactly that order.

Approach

  1. Define walk(node): if node is null, return.
  2. Call walk(node.left), then walk(node.right).
  3. Append node.val to the result.
  4. Call walk(root) and return the result.

Why it works

By induction on the height: walk lists a subtree in postorder because it first lists the left subtree in postorder, then the right one, then the subtree's root — which is the definition. An iterative alternative runs preorder with the children swapped (node, right, left) and reverses the list, since reversing that order gives left, right, node at every level.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion stack, O(n) for a chain-shaped tree

Pitfalls

  • Appending before the recursive calls gives preorder.
  • In the reversed-preorder trick, push the left child before the right one (the reverse of a normal preorder).

Reference solution

Python

from typing import List, Optional

def postorderTraversal(root: Optional[TreeNode]) -> List[int]:
    out = []

    def walk(node):
        if node is None:
            return
        walk(node.left)
        walk(node.right)
        out.append(node.val)

    walk(root)
    return out

Java

public static int[] postorderTraversal(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    postWalk(root, out);
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

static void postWalk(TreeNode node, List<Integer> out) {
    if (node == null) return;
    postWalk(node.left, out);
    postWalk(node.right, out);
    out.add(node.val);
}

C++

void postWalk(TreeNode* node, vector<int>& out) {
    if (!node) return;
    postWalk(node->left, out);
    postWalk(node->right, out);
    out.push_back(node->val);
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> out;
    postWalk(root, out);
    return out;
}

JavaScript

var postorderTraversal = function(root) {
    var out = [];
    postWalk(root, out);
    return out;
};

var postWalk = function(node, out) {
    if (node === null) return;
    postWalk(node.left, out);
    postWalk(node.right, out);
    out.push(node.val);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals