Leetcode 145. Binary Tree Postorder Traversal

Binary Tree Postorder Traversal

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

DFS Recursive Approach 1


class Solution {
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        dfsHelper(root, res);
        return res;
    }
    
    private void dfsHelper(TreeNode node, List res) {
        if (node == null) return; // Base case
        
        dfsHelper(node.left, res);
        dfsHelper(node.right, res);
        res.add(node.val);
    }
}

Time and Space Complexity: O(n)

BFS Iterative Approach 2


class Solution{
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null) return result;
        
        Stack stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(0, node.val); // Add node value at the beginning to simulate postorder
            
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        
        return result;
    }
}

Time and Space Complexity: O(n)

Morris Traversal algorithm for postorder traversal of a binary tree Approach 3:


class Solution{
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        TreeNode dummy = new TreeNode(-1); // Dummy node to handle edge case where root has only one child
        dummy.left = root;
        TreeNode current = dummy;

        while (current != null) {
            if (current.left == null) {
                current = current.right;
            } else {
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    predecessor.right = current;
                    current = current.left;
                } else {
                    reverseAddToList(current.left, predecessor, result);
                    predecessor.right = null;
                    current = current.right;
                }
            }
        }

        return result;
    }
    
    private void reverseAddToList(TreeNode from, TreeNode to, List result) {
        reverse(from, to);
        TreeNode node = to;
        while (true) {
            result.add(node.val);
            if (node == from) break;
            node = node.right;
        }
        reverse(to, from);
    }

    private void reverse(TreeNode from, TreeNode to) {
        if (from == to) return;
        TreeNode x = from;
        TreeNode y = from.right;
        TreeNode z;
        while (true) {
            z = y.right;
            y.right = x;
            x = y;
            y = z;
            if (x == to) break;
        }
    }

}

Time Complexity: O(n) and Space Complexity: O(1)

See Video lecture

Leetcode 102. Binary Tree Level Order Traversal

Introduction

Postorder traversal is one of the fundamental tree traversal methods used in binary trees. It is a **depth-first traversal** technique where nodes are visited in the following order:

Traverse the left subtree.
Traverse the right subtree.
Visit the root node.

This traversal method is particularly useful in applications like evaluating expressions in expression trees or deleting a tree structure recursively.

Problem Statement

Given the root of a binary tree, return its **postorder traversal** as a list of node values.

Example

Consider the binary tree:

The postorder traversal output is:

        [4, 5, 2, 3, 1]

Approach

The essence of postorder traversal is that the root node is processed last. This can be achieved either recursively or iteratively.

Recursive Solution

The recursive approach involves calling the function for the left and right subtrees before processing the root node.

Steps to Solve

If the current node is null, return.
Recursively traverse the left subtree.
Recursively traverse the right subtree.
Add the current node's value to the result list.

Implementation


import java.util.*;

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

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

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

    private void traverse(TreeNode node, List result) {
        if (node == null) {
            return;
        }

        traverse(node.left, result);
        traverse(node.right, result);
        result.add(node.val);
    }
}

Iterative Solution

The iterative approach uses a stack to simulate the recursive function calls. Additionally, it ensures that the root is processed last by pushing nodes onto the stack in a specific order.

Steps to Solve

Initialize two stacks: one for traversal and the other for the final result.
Push the root node onto the traversal stack.
Pop a node from the traversal stack and push it onto the result stack.
Push the left and right children of the popped node onto the traversal stack.
After processing all nodes, pop from the result stack to retrieve the postorder traversal.

Implementation


import java.util.*;

class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack stack = new Stack<>();
        Stack output = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            output.push(current);

            if (current.left != null) {
                stack.push(current.left);
            }
            if (current.right != null) {
                stack.push(current.right);
            }
        }

        while (!output.isEmpty()) {
            result.add(output.pop().val);
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is processed once.
Space Complexity: O(h), where h is the height of the tree (for recursion or stack).

Applications of Postorder Traversal

Expression Trees: Evaluates expressions in postfix notation.
Tree Deletion: Used to delete all nodes of a tree.
Tree Cloning: Creates a copy of a tree by traversing and copying nodes.

Common Mistakes

Failing to handle an empty tree, which should return an empty list.
Not considering edge cases, such as a single-node tree or an unbalanced tree.
Mixing up the order of traversal (left, right, root).

Edge Cases

An empty tree (return an empty list).
A tree with only one node (return a list with the root value).
An unbalanced tree where nodes exist only on one side.

Sample Outputs

Example 1

Tree:

Postorder traversal:

        [4, 5, 2, 3, 1]

Example 2

Tree:

Postorder traversal:

        [3, 2, 1]

Conclusion

Postorder traversal is a critical binary tree traversal technique with extensive applications in tree-related problems. Understanding both recursive and iterative implementations enhances problem-solving skills and prepares you for advanced tree-based challenges.