Binary Tree Postorder Traversal

Question

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

Analysis

  A
 / \
B   C

Remember how we build the preorder traversal. A -> B -> C

If we change the order B and C, A -> C -> Band reverse the order, then we get the postorder traversal. B -> C -> A

Solution : Iterative

class Node(object):

    def __init__(self, value, left=None, right=None):
        self.value = value  # The node value
        self.left = left    # Left child
        self.right = right  # Right child

def postorder_tra(root):
    res = []
    tra_stack = [root]
    while tra_stack:
        tmp = tra_stack.pop()
        res.append(tmp.value)
        if tmp.left:
            tra_stack.append(tmp.left)
        if tmp.right:
            tra_stack.append(tmp.right)
    return res[::-1]