Binary Tree Inorder Traversal

Problem: Binary Tree Inorder Traversal

We use a stack to maintain tree nodes. If top-of-stack node has left child, push left child into stack. If top-of stack node has right child, pop the node first then push its right child.

Code in Python:

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

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root: return []
        stack, ans = [root], []
        while stack:
            if stack[-1].left:
                stack.append(stack[-1].left)
                stack[-2].left = None
                continue
            node = stack.pop()
            ans.append(node.val)
            if node.right:
                stack.append(node.right)
        return ans