# [Binary tree] LeetCode 94. Inorder traversal of binary tree [simple]

Given a root node root of a binary tree, return its inorder traversal .

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root=[]
output: []

Example 3:

Input: root=[1]
Output: [1]

hint:

The number of nodes in the tree is in the range [0, 100]
-100 <= Node.val <= 100

Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?

[analyze]

Knowledge point review:

Pre/preorder traversal: root left right

Inorder traversal: left root right

Postorder Traversal: Left Right Root

Method 1: recursive implementation

Recursive implementation is too simple

• Preorder traversal: print - left - right
• Inorder traversal: left - print - right
• Post-order traversal: left-right-print

The title requires in-order traversal, then the tree can be traversed in the order of left-print-right. The recursive function is implemented

• Termination condition: when the current node is empty
• Inside the function: recursively call the left node, print the current node, and then recursively call the right node

Time complexity: O(n)

Space complexity: O(h), h refers to the height of the tree

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def dfs(root):
if not root:
return
dfs(root.left)
res.append(root.val) # Pay attention to the value writing " root.val"
dfs(root.right)
dfs(root)
return res```

Method 2: Iterative Implementation

The real difficulty of this problem is how to do it in a non-recursive way.

The recursive implementation is that the function calls itself, and the calls are nested layer by layer. The operating system automatically helps us to use the stack to save each called function. Now we need to simulate such a calling process by ourselves.

The recursive calling process is as follows:

```dfs(root.left)
dfs(root.left)
dfs(root.left)
for null return
# print node
dfs(root.right)
dfs(root.right)
dfs(root.right)
......```

The recursive calling process is to keep walking to the left. When the left side can't go any further, it prints the node, turns to the right, and then continues the process on the right.

When we implement iteratively, we can use the stack to simulate the above calling process.

Time complexity: O(n),

Space complexity: O(h), where h is the height of the tree.

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
while stack or root:
# Keep walking in the direction of the left subtree, and save the current node to the stack every time you walk
# This is the call to simulate recursion
if root:
stack.append(root)
root = root.left
# The current node is empty, indicating that the left side has come to the end, pop the node from the stack and save it
# Then turn to the right node and continue the whole process above
else:
tmp = stack.pop()
res.append(tmp.val) # Pay attention to the writing of the value
root = tmp.right
return res```

Method 3: Morris Traversal

Auxiliary space is used both recursively and iteratively, and Morris traversal has the advantage that no auxiliary space is used. The disadvantage is that the structure of the entire tree is changed, and a binary tree is forcibly changed into a linked list structure.

We attach the yellow area to the right subtree of node 5 (orange arrow), and then attach the two nodes 2 and 5 to the right of node 4. In this way, the entire tree basically becomes a linked list, and then it continues to traverse to the right.

Time complexity: O(n), the complexity of finding each predecessor node is O(n), because the binary tree of n nodes has n-1 edges, and each edge can only be used twice (once to locate the node, Find the predecessor node at a time), so the time complexity is O(n).

Space complexity: O(1), no additional auxiliary space is used.

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
pre = None
while root:
# If the left node is not empty, hang the current node and the right subtree below the rightmost subtree of the left node
if root.left:
pre = root.left
while pre.right:
pre = pre.right
pre.right = root
# Will root direction root of left
tmp = root
root = root.left
tmp.left = None
# If the left subtree is empty, print this node and traverse to the right
else:
res.append(root.val)
root = root.right
return res

# author: wang_ni_ma