## Tree Node Definition#

``````# Definition for a binary tree node.
from typing import List

class TreeNode:
def __init__(self, x: int) -> None:
self.val = x
self.left = None
self.right = None
``````

## Recursive Implementation#

### `left` ➡️ `root` ➡️ `right`#

``````class Solution:
def traversal(self, root: 'TreeNode', result=None) -> List[List[int]]:
"""
0
/     \
1        2
/   \
3       4
/   \
6       9

In-order...: [3, 1, 6, 4, 9, 0, 2]

T: O(N)
S: O(N) worst case; O(log N) average
"""

if result is None:
result = []

if not root:
return []

self.traversal(root.left, result=result)
out.append(root.val)
self.traversal(root.right, result=result)

return result
``````

## Iterative Implementation#

`left` ➡️ `root` ➡️ `right`

``````class Solution:
def traversal(self, root: 'TreeNode')->List[List[int]]:
"""
0
/     \
1        2
/   \
3       4
/   \
6       9

In-order...: [3, 1, 6, 4, 9, 0, 2]

T: O(N)
S: O(N)
"""
if not root:
return []

stack = []
result = []
node = root

while node or stack:
# Traverse down to bottom of the left branch
while node:
stack.append(node)
node = node.left

# Visit root and then go right
node = stack.pop()
result.append(node.val)
node = node.right

return result
``````