Leetcode Daily Question 25/08/2024 - 145. Binary Tree Postorder Traversal

Problem Description:

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

Solution: ►

class TreeNode:
  def __init__(self,val = 0, left = None, right = None):
    self.val = val
    self.left = left
    self.right = right
    
from typing import List, Optional
class Solution:
  def postOrderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    def helper(node):
      if node:
        helper(node.left)
        helper(node.right)
        result.append(node.val)
    
    result = []
    helper(root)
    return result

Explanation:

There are 3 types of traversal methods for a binary tree.

- Post-Order Traversal
- Pre-Order Traversal
- In-Order Traversal

Let's start with in-order, this is the "natural" way to traverse the tree. "Bottom left up" - start with left subtree then visit root then right subtree.

Pre-order is "top down root first" - start with root then visit left subtree then right subtree.

Post-order is "root last bottom left" - start with left subtree then right subtree then root.

Take the example tree

1
| \ 
2  5
| \
3  4

Our helper function to start from the root, then go all the way down to 3, then 4, then 2, then 5, then 1 in that order.

Here is a way to do it using a recursive helper function.

#postorder helper
def helperPostOrder(node):
  if node:
  	helperPostOrder(node.left)
  	helperPostOrder(node.right)
  	result.append(node.val)

Since we are discussing traversal methods, let's define the helper functions for those first.

The idea is the same, the recursion is the same, it is when we should note down the value that differs.

# preorder helper
def helperPreOrder(node):
  if node:
    result.append(node.val)
    helperPreOrder(node.left)
    helperPreOrder(node.right)
# inorder helper
def helperInOrder(node):
  if node:
    helperInOrder(node.left)
    result.append(node.val)
    helperInOrder(node.right)

The time complexity of all of these methods are O(n) as we need to traverse every node once.

The space complexity of all these methods are O(n) as well, since we need to store the values of the nodes.

The full solution can be found near the top of the page.

Back