# Solution by awice

• #### Approach #1: Recursive [Accepted]

Intuition and Algorithm

An in-order traversal means for each node, traverse the left, then act on the node, then traverse the right. The most straightforward way is a recursive solution.

Python

``````class Solution(object):
def inorderTraversal(self, root):
ans = []
def inorder(node):
if node:
inorder(node.left)
ans.append(node.val)
inorder(node.right)

inorder(root)
return ans
``````

Complexity Analysis

• Time Complexity: \$\$O(N)\$\$, where \$\$N\$\$ is the number of nodes in the given binary tree.

• Space Complexity: \$\$O(N)\$\$, where \$\$N\$\$ is as defined above. Our final answer will contain all values inside the tree.

#### Approach #2: Iterative [Accepted]

Intuition

If somehow we could emulate the call stack that is used by our compiler (or interpreter) to nest the recursive functions, we could then proceed iteratively.

Algorithm

The commands `inorder(node.left)` and `inorder(node.right)` get converted to the actions `(VISIT, node.left)` and `(VISIT, node.right)`. The command `ans.append(node.val)` gets converted to the action `(DO, node)`.

`stack` emulates the behavior of the call stack: keeping a stack of actions to perform. We need to be careful to place things on the stack in the reverse order of when we want them done, as actions are popped from the end.

To prevent mistakes and provide for clarity of code, we define enumeration constants `VISIT` and `DO`.

Python

``````class Solution(object):
def inorderTraversal(self, root):
VISIT, DO = 0, 1
ans = []
stack = [(VISIT, root)]
while stack:
command, node = stack.pop()
if node:
if command is VISIT:
stack.append((VISIT, node.right))
stack.append((DO, node))
stack.append((VISIT, node.left))
else:
ans.append(node.val)

return ans
``````

Complexity Analysis

• Time Complexity: \$\$O(N)\$\$, where \$\$N\$\$ is the number of nodes in the given binary tree.

• Space Complexity: \$\$O(N)\$\$, where \$\$N\$\$ is as defined above. Our final answer will contain all values inside the tree.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.