Binary Tree Postorder Traversal-null

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

Question

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

Example:

Input:{1,2,3}
Output:[2,3,1]

Explanation:
  1
 / \
2  3

Input:{1,2,#,3,4}
Output:[3,4,2,1]

Explanation:
    1
   /
  2
 / \
3  4

Analyzation

Stack

Firstly, push the dummy node into the stack.

Secondly, append the current node’s val to the result list and push the right child to the stack.

Thirdly, append all the right children to the stack till the very right, and append the value to the result list.

Finally, reverse the whole result list because we find the root val first, right value next, and left value last.

The Code

class Solution:
    """
    @param root: A Tree
    @return: Postorder in ArrayList which contains node values.
    """
    # Non-Recursive method
    def postorderTraversal(self, root):
        if root is None:
            return []
        
        dummy = TreeNode(0)
        dummy.left = root
        stack = [dummy]
        result = []
        
        while stack:
            node = stack.pop()
            node = node.left
            
            while node:
                result.append(node.val)
                stack.append(node)
                node = node.right
        
        return result[::-1]

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).