algoadvance

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

In postorder traversal, the nodes are recursively visited as follows:

1. Visit the left subtree.
2. Visit the right subtree.
3. Visit the root node.

Clarifying Questions

1. What should we return if the tree is empty?
   • Return an empty list.
2. Can the tree contain duplicate values?
   • Yes, the tree may contain duplicate values.
3. What data structure is used for the binary tree?

   • The binary tree nodes use classes, typically defined as:

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

4. Is there any constraint on the height of the tree?
   • There are no explicit constraints mentioned on the height of the tree.

Strategy

We can solve this problem using two main approaches:

1. Recursive Approach:
   • Recursively visit the left subtree, then the right subtree, and finally the root node.
2. Iterative Approach:
   • Use a stack to simulate the call stack of the recursion. Keep track of the nodes and the state of their traversal.

Code

Here are both approaches in Python:

Recursive Approach

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

def postorderTraversal(root: TreeNode):
    def helper(node, result):
        if node:
            helper(node.left, result)
            helper(node.right, result)
            result.append(node.val)
    
    result = []
    helper(root, result)
    return result

Iterative Approach

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

def postorderTraversal(root: TreeNode):
    if not root:
        return []

    stack, output = [root], []

    while stack:
        node = stack.pop()
        output.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return output[::-1]

Time Complexity

Both approaches have the same time complexity:

• Time Complexity: (O(n))
  • Every node is visited exactly once.
• Space Complexity:
  • Recursive Approach: (O(h)) where (h) is the height of the tree due to the recursion stack.
  • Iterative Approach: (O(n)) where (n) is the number of nodes, mainly due to the stack used for traversal.

Choose an approach based on the preference for recursion or iteration and constraints such as recursion depth.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?