Binary Tree Postorder Traversal (Leet Code-145)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 94. This is a Leet code problem named Binary Tree Postorder Traversal. We will solve it using python and it is the best space and time-optimized solution.

Question of Binary Tree Postorder Traversal

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

In In-Order Traversal we simply traverse in the LRN format. In LRN format, we first read the left node, then the right side of the node, and at last the root node.

Example

Example 1

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2

Input: root = []
Output: []

Example 3

Input: root = [1]
Output: [1]

Constraints

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Approach to solve Binary Tree Postorder Traversal

To solve this problem we will first visit through the left node after that we visit the right node and at last, we visit the root node in a recursive manner.

Algorithm

This method performs the following steps for a given input array:

Create nodes array to store nodes.
Create an inner function to do recursion.
Check if the root exists. If yes then go to step 4 otherwise break inner function.
Call left child of root recursively.
Call right child of root recursively.
append the value of root to node variable.
End if
End inner function
return node

Python Code for Binary Tree Postorder Traversal

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        if root is None:
            return None
        elements = []
        if root.left:
            elements += self.postorderTraversal(root.left)
        if root.right:
            elements += self.postorderTraversal(root.right)

        elements.append(root.val)

        return elements