Binary Tree Inorder Traversal

Problem Id: 94 Difficulty: Medium Tag: Tree Tag: Hash Table Tag: Stack


Intuition

The recurisive way is really simple. Let's consider the non-recurisive way, which is using stack.

If we pay attention to the recurisive way of inorder traversal, we will notice that the _helper is recurisivly called twice in the recurisive code. So for non-recurisive way, we would need 2 different stack. The first one is for saving the nodes whose left node has not been visited. The second one if for saving the nodes whose left node has already been visited while itself and right node has not been visited.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# Below are the recurisive source code.
# class Solution:
#     def inorderTraversal(self, root):
#         self.inorder = []
#         self._helper(root)
#         return self.inorder
# 
#     def _helper(self, node):
#         if node is None:
#             return
#         self._helper(node.left)
#         self.inorder.append(node.val)
#         self._helper(node.right)


class Solution:
    def inorderTraversal(self, root):
        if root is None:
            return
        inorder = []
        prestack = [root]
        instack = []
        while prestack or instack:
            if prestack:
                node = prestack.pop()
                instack.append(node)
                if node.left:
                    prestack.append(node.left)
            elif instack:
                node = instack.pop()
                inorder.append(node.val)
                if node.right:
                    prestack.append(node.right)
        return inorder