Binary Tree Postorder Traversal - Leetcode Solution

Binary Tree Postorder Traversal is a problem on LeetCode which asks to traverse a given binary tree in post-order, i.e., first visit left and right subtrees recursively and then visit the root node.

The problem provides the following definition of a binary tree node:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

And the function signature is given as:

def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

The function takes in a root node of the binary tree and returns a list of integers representing the post-order traversal.

Approach:

The post-order traversal of a binary tree can be done using the recursive approach, where we first traverse left and right subtrees recursively, and then visit the root node.

The basic idea for the recursive approach is to call the function recursively for the left subtree and append the result to the traversal list; then call the function recursively for the right subtree and append the result to the traversal list; finally, append the root node value to the traversal list.

Algorithm:

1. Initialize an empty list traversal to store the nodes in post-order.
2. Define a recursive function postorder that takes a node as an argument: a. If the node is not null: i. Recursively call postorder on the left subtree. ii. Recursively call postorder on the right subtree. iii. Append the node's value to the traversal list.
3. Call the postorder function with the input binary tree's root node.
4. Return the traversal list.

Code:

The Python implementation of the above algorithm is given below:

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        traversal = []
        
        def postorder(node):
            if node:
                postorder(node.left)
                postorder(node.right)
                traversal.append(node.val)
        
        postorder(root)
        
        return traversal

Complexity Analysis:

The time complexity of the above algorithm is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

The space complexity of the above algorithm is O(n), where n is the number of nodes in the binary tree. This is because the recursion stack can have at most n nodes in it.

1