Binary Tree Postorder Traversal

Given the root of a binary tree, traverse the tree in postorder fashion and return a list containing the values of the nodes in the order they are visited. Postorder traversal involves visiting the left subtree, then the right subtree, and finally the root node itself. This traversal is useful in scenarios like evaluating expressions represented as trees or deleting nodes in a way that avoids memory leaks.

Problem Description

You are tasked with implementing a function that performs a postorder traversal of a binary tree. The binary tree is represented using a node structure where each node has a value, a left child, and a right child. Your function should return a list of integers, where each integer represents the value of a node visited during the postorder traversal.

What needs to be achieved:

• Implement a postorder traversal algorithm.
• Return a list containing the node values in the order they are visited.

Key requirements:

• The traversal must follow the postorder sequence: Left -> Right -> Root.
• The function should handle empty trees gracefully.
• The function should correctly traverse trees of varying depths and structures.

Expected behavior:

The function should take the root node of a binary tree as input and return a list of integers representing the postorder traversal.

Edge cases to consider:

• Empty tree (root is null/None).
• Tree with only a root node.
• Skewed trees (left-skewed or right-skewed).
• Trees with deeply nested nodes.

Examples

Example 1:

Input: root = [1,null,2,3]
     1
    / \
   3   2
Output: [3,2,1]
Explanation: The postorder traversal is: visit 3 (left), visit 2 (right), visit 1 (root).

Example 2:

Input: root = []
Output: []
Explanation: An empty tree results in an empty list.

Example 3:

Input: root = [1]
Output: [1]
Explanation: A tree with only a root node results in a list containing only the root's value.

Constraints

• The number of nodes in the tree can range from 0 to 1000.
• The values of the nodes are integers.
• The tree can be unbalanced.
• The solution should have a time complexity of O(N), where N is the number of nodes in the tree.
• The solution should have a space complexity of O(H) in the average case, where H is the height of the tree (due to the recursion stack), and O(N) in the worst case (skewed tree).

Notes

Consider using recursion to implement the postorder traversal. Think about the base case for the recursion (when to stop). Remember the order of operations: Left, Right, Root. You can also implement this iteratively using a stack, but recursion is often a more straightforward approach for tree traversals.