Binary Tree Postorder Traversal

Postorder Traversal

Question

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

Example:

Input：{1,2,3}
Output：[2,3,1]
Explanation:  
   1
  / \
 2   3
 it will be serialized {1,2,3}
Post order traversal


Input：{1,#,2,3}
Output：[3,2,1]
Explanation:  
1
 \
  2
 /
3
it will be serialized {1,#,2,3}
Post order traversal

Analyzation

Recursion

Follow the path of “Root -> Left -> Right” and do the recursion.

Note that “+=” is almost the same as “.extend” and the only difference is that the “.extend” evolves a function call so it is slightly more expensive in Python. Here we cannot use “.append” because in this way it will append empty lists because it is a recursive call.

The Code

class Solution {
    """
    @param root: A Tree
    @return: Postorder in ArrayList which contains node values.
    """
    def postorderTraversal(self, root):
        # write your code here
        result = []
        if root:
            result.extend(self.postorderTraversal(root.left))
            result.extend(self.postorderTraversal(root.right))
            result.extend([root.val])
        
        return result
}


class Solution:
    """
    @param root: A Tree
    @return: Postorder in ArrayList which contains node values.
    """
    def postorderTraversal(self, root):
        # write your code here
        result = []
        if root:
            result += self.postorderTraversal(root.left)
            result += self.postorderTraversal(root.right)
            result += [root.val]
        
        return result

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).