---
link: https://leetcode.com/problems/binary-tree-inorder-traversal/
tags: tree, bt
---

# 94. Binary Tree Inorder Traversal
## Question
Given a binary tree, return the *inorder* traversal of its nodes' values.

**Example:**

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

**Follow up:** Recursive solution is trivial, could you do it iteratively?

## Solution: 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 inorderTraversalRecursive(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        self.helper(root, result)
        return result
    
    def helper(self, node, result):
        if node is None:
            return
        
        self.helper(node.left, result)
        result.append(node.val)
        self.helper(node.right, result)

    def post_order_helper(self, node, result):
        if node is None:
            return
        
        self.helper(node.left, result)
        self.helper(node.right, result)
        result.append(node.val)
    
    def pre_order_helper(self, node, result):
        if node is None:
            return
        result.append(node.val)  # A
        self.helper(node.left, result)  # B
        self.helper(node.right, result)  # C
        
        
    def inorderTraversal(self, root):
        from collections import deque
        stack = deque()
        stack.append((False, root))  # IsAppendingResult, Node
        result = []
        
        while stack:
            is_appending_result, node = stack.pop()
            
            if node is None:
                continue
            if is_appending_result:
                result.append(node.val)
            else:
                stack.extend([(False, node.right), (False, node.left), (True, node)])  # Pre order
                stack.extend([(False, node.right), (True, node), (False, node.left)])  # In order
                stack.extend([(True, node), (False, node.right), (False, node.left)])  # Post order
                stacl.extend([C, B, A])
        return result

"""
    1
     \
      2
     /
    3

stack=[(False, 1)], result=[]
stack=[(False, 2), (True, 1), (False, None)], result=[]
stack=[(False, 2), (True, 1)], result=[]
stack=[(False, 2)], result=[1]
stack=[(False, None), (True, 2), (False, 3)], result=[1]
stack=[(False, None), (True, 2), (False, None), (True, 3), (False, None)], result=[1]
stack=[(False, None), (True, 2), (False, None), (True, 3)], result=[1]
stack=[(False, None), (True, 2), (False, None)], result=[1, 3]
stack=[(False, None), (True, 2)], result=[1, 3]
stack=[(False, None)], result=[1, 3, 2]
stack=[], result=[1, 3, 2]
"""

## Solution: Java