Binary Tree Postorder Traversal

NeetCode: Binary Tree Postorder Traversal · LeetCode: 145. Binary Tree Postorder Traversal · Difficulty: Easy

Given the root of a binary tree, return the postorder traversal of its node values: visit the left subtree, then the right subtree, then the node itself.

Example

Text

Input:  [1, null, 2, 3]     (1 has right child 2, and 2 has left child 3)
Output: [3, 2, 1]

Input:  []
Output: []

Postorder visits every node after all of its descendants, which is the right order for deleting a tree or for computing something bottom-up.

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Brute force: recursion

Recurse into the left subtree, then the right subtree, then record the node. The result is a List<Integer>; an ArrayList holds the values in the order they are added.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private void walk(TreeNode node, List<Integer> out) {
        if (node == null) {
            return;
        }
        walk(node.left, out);
        walk(node.right, out);
        out.add(node.val);
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        walk(root, out);
        return out;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.postorderTraversal(tree(1, null, 2, 3)));
        System.out.println(s.postorderTraversal(tree(4, 2, 6, 1, 3, 5, 7)));
        System.out.println(s.postorderTraversal(tree()));
    }
}

Output

[3, 2, 1]
[1, 3, 2, 5, 7, 6, 4]
[]

The recursion depth equals the tree height. A chain of many thousands of nodes can overflow the thread's call stack with a StackOverflowError. Time: O(n). Space: O(h) for the call stack.

Optimal: iterative, reverse a "node, right, left" walk

Postorder is (left, right, node). Reverse that and the order is (node, right, left): a mirror image of preorder. So run an iterative preorder that pushes the left child first and the right child second (visiting right before left), collect the values, and reverse the result at the end. That gives a stack-based postorder with no recursion and no visited flags.

ArrayDeque is the stack. push and pop work at the front, and ArrayDeque rejects null, so the code pushes a child only when it is not null.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root != null) {
            stack.push(root);
        }
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            out.add(node.val); // node, then right, then left ...
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(out); // ... reversed is left, right, node
        return out;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.postorderTraversal(tree(1, null, 2, 3)));
        System.out.println(s.postorderTraversal(tree(4, 2, 6, 1, 3, 5, 7)));
        System.out.println(s.postorderTraversal(tree()));
    }
}

Output

[3, 2, 1]
[1, 3, 2, 5, 7, 6, 4]
[]

Both versions run in O(n); the iterative one avoids deep recursion. Time: O(n). Space: O(n) for the output plus O(h) for the stack.

Interview points

Postorder is left, right, node. Every node is recorded after its descendants.
The iterative form walks node, right, left with a stack and reverses the output.
The recursive form uses O(h) call-stack space and can overflow on very deep trees.

Summary

Time O(n) for both versions.
Recursive space is O(h); iterative space is O(h) for the stack plus the O(n) output.
ArrayDeque does not accept null, so push only existing children.