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', out=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 out is None:
out = []
if not root:
return []
self.traversal(root.left, out=out)
out.append(root.val)
self.traversal(root.right, out=out)
return out
Iterative Implementation
left
➡️ root
➡️ right
from collections import deque
class Solution:
def traversal(self, root: 'TreeNode', out=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)
"""
if out is None:
out = []
if not root:
return []
stack = deque()
curr = root
while curr or stack:
# Traverse down to bottom of the left branch
while curr:
stack.append(curr)
curr = curr.left
# Visit root and then go right
curr = stack.pop()
out.append(curr.val)
curr = curr.right
return out