Postorder Traversal

Postorder Traversal#

Introduction #

Postorder traversal is a method used in binary trees to visit all the nodes in a defined order: first visit the left child, then the right child, and finally the root node. This method is applied recursively to all subtrees of the tree.

Traverse the left subtree in Postorder.
Traverse the right subtree in Postorder.
Visit the root.

Let’s break down the process more:

Visit the left subtree: The traversal begins with the left subtree. This isn’t just a single node visit; it involves the whole subtree, implying that the traversal follows the same set of rules, i.e., visiting its left child, right child, and then the root node. If the left subtree is empty (no nodes to visit), this step is skipped.
Visit the right subtree: After the left subtree has been traversed, the algorithm moves to the right subtree following the same set of rules: visiting its left child, right child, and then the root node. If the right subtree is empty, this step is also skipped.
Visit the root node: Only after visiting all the nodes in both subtrees does the algorithm visit the root node of the current subtree.

It’s important to note that steps 1 and 2 involve recursion, meaning they will apply the same three steps to each subtree they visit. This recursion continues until it reaches a tree with no children (known as a leaf node), which marks the base case for the recursion.

Example #

For our example tree:

      1
   __/ \_
  2      6
 / \    / \
3   4  7   9
   /  /
  5  8

The order of nodes visited during a postorder traversal is:

3-5-4-2-8-7-9-6-1

Here’s how you’d perform a postorder traversal on this example tree:

Visit all nodes in the left subtree of 1:
- Visit all nodes in the left subtree of 2:
  - Visit all nodes in the left subtree of 3. The left subtree of 3 is None, so there are no nodes to visit.
  - Visit all nodes in the right subtree of 3. The right subtree of 3 is None, so there are no nodes to visit.
  - Visit the root of this subtree: 3.
- Visit all nodes in the right subtree of 2:
  - Visit all nodes in the left subtree of 4:
    - Visit all nodes in the left subtree of 5. The left subtree of 5 is None, so there are no nodes to visit.
    - Visit all nodes in the right subtree of 5. The right subtree of 5 is None, so there are no nodes to visit.
    - Visit the root of this subtree: 5.
  - Visit all nodes in the right subtree of 4. The right subtree of 4 is None, so there are no nodes to visit.
  - Visit the root of this subtree: 4.
- Visit the root of the left subtree: 2.
Visit all nodes in the right subtree of 1:
- Visit all nodes in the left subtree of 6:
  - Visit all nodes in the left subtree of 7:
    - Visit all nodes in the left subtree of 8. The left subtree of 8 is None, so there are no nodes to visit.
    - Visit all nodes in the right subtree of 8. The right subtree of 8 is None, so there are no nodes to visit.
    - Visit the root of this subtree: 8.
  - Visit all nodes in the right subtree of 7. The right subtree of 7 is None, so there are no nodes to visit.
  - Visit the root of this subtree: 7.
- Visit all nodes in the right subtree of 6:
  - Visit all nodes in the left subtree of 9. The left subtree of 9 is None, so there are no nodes to visit.
  - Visit all nodes in the right subtree of 9. The right subtree of 9 is None, so there are no nodes to visit.
  - Visit the root of this subtree: 9.
- Visit the root of the right subtree: 6.
Visit the root node: 1.

Therefore, the order of nodes visited during an post-order traversal of this tree is 3-5-4-2-8-7-9-6-1. The process is recursive, and the same set of rules is applied to each subtree within the tree. As with preorder, any recursive process can also be implemented iteratively; we can implement an post-order traversal of a binary tree iteratively using a stack.

Visualization #

See leetcode’s visualization of Inorder.

Problem #

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

Intuition #

For postorder traversal, you can still use the family gathering analogy, but now with an even different rule of introduction:

Parents tell children: “Before I introduce myself, I want both of my children (if they exist) to introduce themselves first, along with their own children (if any), following the same rule. My left child and their descendants will go first, then my right child and their descendants will go. Only after everyone else in our family has introduced themselves will I introduce myself.”
Children follow their parent’s instructions: Each child node in the tree considers itself as the parent of its own subtree. They first ask their left child (if any) to introduce themselves and their descendants, then they ask their right child (if any) to introduce themselves and their descendants, following the same rules. Only after both of their “children” have gone will they introduce themselves.

This parent-child communication continues until all nodes in the tree have been visited, ensuring a complete postorder traversal of the tree.

In essence, each node in a postorder traversal defers its own visit until after all of its descendants (its entire left and right subtrees) have been visited. A node’s left subtree corresponds to everyone who introduces themselves before the right subtree, and the right subtree corresponds to everyone who introduces themselves before the node itself.

So, in a postorder traversal, everyone in the left subtree introduces themselves first, followed by everyone in the right subtree, and finally the node itself.

Assumptions #

The input is a binary tree where a node can have at most two children.
The binary tree does not have to be balanced.
The binary tree can be empty, which means the root can be None.
- So make sure to handle this edge case in your code!
Each node contains an integer value.

Constraints #

The number of nodes in the tree is in the range:

\[ 0 \leq \text{number of nodes} \leq 100 \]

This constraint specifies the minimum and maximum size of the binary tree that our algorithm needs to handle. Knowing this, we can evaluate whether our solution would scale efficiently for the largest possible input size. For example, a solution with a time complexity of \(\mathcal{O}(n)\), where \(n\) is the number of nodes in the tree, would likely be acceptable.
Each node’s value is an integer in the range:

\[ -100 \leq \text{Node.val} \leq 100 \]

This constraint informs us about the range of values that each node in the tree can hold. It is important to take this into account when considering possible edge cases. However, for this particular problem of preorder traversal, the actual values of the nodes do not affect the traversal order.

What are Constraints for?#

In programming problems, constraints are given to define the scope and limits of the problem. They help to determine the feasible approaches and solutions for the problem by providing information about the range and characteristics of the input data. They help us anticipate the worst-case scenarios that our algorithm should be able to handle without leading to inefficiencies or failures, like time limit exceeded or memory limit exceeded errors.

Test Cases #

Normal case: A tree with more than one node.

root = build_binary_tree_from_list_preorder(
    [1, 2, 4, None, None, 5, None, None, 3, 6, None, None, 7, None, None]
)
assert postorder_traversal(root) == [4, 5, 2, 6, 7, 3, 1]

Unbalanced tree: A tree where one side has more nodes than the other side.

root = build_binary_tree_from_list_preorder([1, 2, None, 3, None, 4, None, None])
assert postorder_traversal(root) == [2, 4, 3, 1]

Tree with single path: A tree where each parent has only one child.

root = build_binary_tree_from_list_preorder([1, 2, None, 3, None, 4, None, None])
assert postorder_traversal(root) == [4, 3, 2, 1]

Tree with duplicate values: A tree with duplicate values in nodes.

root = build_binary_tree_from_list_preorder([1, 1, None, 1, None, 1, None, 1, None, None])
assert postorder_traversal(root) == [1, 1, 1, 1, 1]

Edge Cases #

Empty tree: A tree with no nodes. This is a valid input and should return an empty list.

root = build_binary_tree_from_list_preorder([])
assert postorder_traversal(root) == []

Single node: A tree with only one node. This edge case tests whether the function can handle the smallest non-empty tree.
```
root = build_binary_tree_from_list_preorder([1])
assert postorder_traversal(root) == [1]
```
Tree with maximum allowed nodes: This edge case tests if the function can handle the largest possible tree within the constraints. Given the constraint that each node’s value is unique, the input list will follow the pattern of descending to the leftmost node and then filling in the right subtree at each level before moving down to the next level.
```
root = build_binary_tree_from_list_preorder(list(range(99, -1, -1)))
assert postorder_traversal(root) == list(range(0, 100))
```
Tree with minimum and maximum allowed node values: This edge case tests if the function can handle the smallest and largest possible node values within the constraints.
```
root = build_binary_tree_from_list_preorder([-100, None, 100])
assert postorder_traversal(root) == [100, -100]
```

Walkthrough / Whiteboarding #

Consider the binary tree below:

The postorder traversal sequence for this tree is 4, 5, 2, 3, 1.

First, traverse the left subtree of root node 1. Visit 2, then go left and visit 4.
For 4, both left and right are None, so we are done with 4.
We return to 2, go right and visit 5. For 5, the left and right are None, so we are done with 5.
Now, having traversed both left and right subtrees of 2, we are done with 2.
We return to 1, and proceed to its right subtree. Visit 3. As there are no children for 3, we are done with 3.
Finally, having traversed both left and right subtrees of 1, we are done with 1, hence the traversal is complete.

Theoretical Best Time Complexity #

The theoretical best time complexity for postorder traversal of a binary tree is \(\mathcal{O}(n)\), where \(n\) is the number of nodes in the binary tree. This is because each node is visited exactly once during the traversal.

See preorder traversal for a detailed explanation of why the time complexity is \(\mathcal{O}(n)\).

Theoretical Best Space Complexity #

The theoretical best (auxiliary) space complexity for this problem is \(\mathcal{O}(n)\), where \(n\) is the number of nodes in the binary tree. This is due to the space required by the call stack (assuming a recursive implementation), which grows proportional to the maximum height of the tree (which in worst case could be \(n\)), and the space required to store the output, which would be equal to the number of nodes in the binary tree.

Space-Time Tradeoff #

As with other tree traversals, there isn’t much of a traditional space-time tradeoff in this problem. The traversal is a linear operation with respect to the number of nodes, and the space required is also proportional to the number of nodes. The most efficient solution will always involve visiting each node in the tree once, and the space used is necessary to store the output and accommodate the recursion stack (in case of recursive approach). However, an iterative solution using an explicit stack would have the same space complexity due to the need for storing nodes in a stack data structure.

Solution (Recursive)#

Implementation #

class Solution1:
    def postorderTraversal(self, root: Optional[BinaryTreeNode]) -> List[int]:
        postorder: List[int] = []

        def traverse(root: Optional[BinaryTreeNode], postorder: List[int]) -> List[int]:
            if not root:
                return postorder

            traverse(root.left, postorder)
            traverse(root.right, postorder)
            postorder.append(root.value)
            return postorder

        postorder = traverse(root, postorder)
        return postorder


class Solution2:
    def __init__(self) -> None:
        self.postorder: List[int] = []

    def reset(self) -> None:
        """To reset if the class instance were to traverse a new root."""
        self.postorder = []

    def postorderTraversal(self, root: Optional[BinaryTreeNode]) -> List[int]:
        if not root:
            return

        self.postorderTraversal(root.left)
        self.postorderTraversal(root.right)
        self.postorder.append(root.value)

        return self.postorder

Tests #

postorder_traversal = Solution1().postorderTraversal

def print_and_test_postorder(
    root: Optional[BinaryTreeNode],
    expected_output: List[int],
    case_name: str,
    print_tree: bool = True,
):
    if print_tree:
        print(case_name)
        lines = print_binary_tree(
            root, node_info=lambda n: (str(n.value), n.left, n.right), is_top=False
        )
        print("\n".join(lines))
    compare_test_case(postorder_traversal(root), expected_output, case_name)

# Test Case 1: Normal case
print_and_test_postorder(
    build_binary_tree_from_list_preorder(
        [1, 2, 4, None, None, 5, None, None, 3, 6, None, None, 7, None, None]
    ),
    [4, 5, 2, 6, 7, 3, 1],
    "Normal case",
)

# Test Case 2: Unbalanced tree
print_and_test_postorder(
    build_binary_tree_from_list_preorder([1, 2, None, 3, None, 4, None, None]),
    [4, 3, 2, 1],
    "Unbalanced tree",
)

# Test Case 3: Tree with single path
print_and_test_postorder(
    build_binary_tree_from_list_preorder([1, 2, None, 3, None, 4, None, None]),
    [4, 3, 2, 1],
    "Tree with single path",
)

# Test Case 4: Tree with duplicate values
print_and_test_postorder(
    build_binary_tree_from_list_preorder([1, 1, None, 1, None, 1, None, 1, None, None]),
    [1, 1, 1, 1, 1],
    "Tree with duplicate values",
)

# Edge Case 1: Empty tree
print_and_test_postorder(build_binary_tree_from_list_preorder([]), [], "Empty tree", print_tree=False)

# Edge Case 2: Single node
print_and_test_postorder(build_binary_tree_from_list_preorder([1]), [1], "Single node")

# Edge Case 3: Tree with maximum allowed nodes
print_and_test_postorder(
    build_binary_tree_from_list_preorder(list(range(1, 101))),
    list(range(100, 0, -1)),
    "Tree with maximum allowed nodes",
    print_tree=False,
)

# Edge Case 4: Tree with minimum and maximum allowed node values
print_and_test_postorder(
    build_binary_tree_from_list_preorder([-100, None, 100]),
    [100, -100],
    "Tree with minimum and maximum allowed node values",
)

Normal case
      1
   __/ \_
  2      3
 / \    / \
4   5  6   7

Test passed: Normal case

Unbalanced tree
  1
 /
2
 \
  3
   \
    4

Test passed: Unbalanced tree

Tree with single path
  1
 /
2
 \
  3
   \
    4

Test passed: Tree with single path

Tree with duplicate values
  1
 /
1
 \
  1
   \
    1
     \
      1

Test passed: Tree with duplicate values

Test passed: Empty tree

Single node
1

Test passed: Single node

Test passed: Tree with maximum allowed nodes

Tree with minimum and maximum allowed node values
-100
   \
   100

Test passed: Tree with minimum and maximum allowed node values

Time Complexity #

The time complexity of postorder traversal, similar to the other tree traversals, is \(\mathcal{O}(n)\), where \(n\) is the number of nodes in the tree. This is because the algorithm has to visit every node in the tree once and only once. The specific order of visiting (whether it’s preorder, inorder, or postorder) doesn’t affect the time complexity.

Table 84 Time Complexity of Postorder Traversal Recursive Algorithm#
Case	Worst Case	Average Case	Best Case
Empty Tree	\(\mathcal{O}(1)\)	\(\mathcal{O}(1)\)	\(\mathcal{O}(1)\)
Balanced Tree	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)
Degenerate Tree	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)
Random Tree	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)

Space Complexity #

The space complexity for the postorder traversal follows the same pattern as other depth-first tree traversals.

Input Space Complexity #

The input space complexity remains the same, i.e., \(\mathcal{O}(n)\).

Auxiliary Space Complexity #

The auxiliary space complexity for a recursive solution is dependent on the maximum depth of the recursion, which corresponds to the height of the tree. For a balanced tree, the height is \(\mathcal{O}(\log n)\), whereas for a degenerate tree (worst case), the height is \(\mathcal{O}(n)\).

Table 85 Auxiliary Space Complexity of Postorder Traversal Recursive Algorithm#
Case	Auxiliary Space Complexity
Empty Tree	\(\mathcal{O}(1)\)
Balanced Tree	\(\mathcal{O}(\log n)\)
Degenerate Tree	\(\mathcal{O}(n)\)

Total Space Complexity #

Summing up the input and auxiliary space complexity gives the total space complexity:

Table 86 Total Space Complexity of Postorder Traversal Recursive Algorithm#
Case	Total Space Complexity
Empty Tree	\(\mathcal{O}(1)\)
Balanced Tree	\(\mathcal{O}(n)\)
Degenerate Tree	\(\mathcal{O}(n)\)

Thus, the time complexity of postorder traversal is linear with respect to the number of nodes, and the space complexity is linear in the worst case (when the tree degenerates into a linked list), but logarithmic in the case of a balanced tree.

Leetcode Solution
Leetcode Card: Traverse a Tree
Tree Traversal Time Complexity
Time Complexity of Binary Tree Preorder