Approach #1: Recursive [Accepted]
Intuition and Algorithm
An inorder 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.