Tree Traversal
Tree traversal is the process of visiting each node in a tree data structure exactly once in a systematic way.
Depth First Search
144. Binary Tree Preorder Traversal
Explanation
- Recursive
- Iterative
- Morris Traversal
Interactive Visualization
Analysis
- Python
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node):
if not node:
return
result.append(node.val)
dfs(node.left)
dfs(node.right)
result = []
dfs(root)
return result
Interactive Visualization
Analysis
- Python
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = collections.deque([(root, False)])
result = []
while stack:
node, visited = stack.pop()
if node:
if visited:
result.append(node.val)
else:
stack.append((node.right, False))
stack.append((node.left, False))
stack.append((node, True))
return result
- Python (Simplified)
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = collections.deque([root])
result = []
while stack:
node = stack.pop()
if node:
result.append(node.val)
stack.append(node.right)
stack.append(node.left)
return result
Interactive Visualization
Analysis
- Python
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
current = root
while current:
if not current.left:
result.append(current.val)
current = current.right
else:
# Find inorder predecessor
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
result.append(current.val)
predecessor.right = current
current = current.left
else:
predecessor.right = None
current = current.right
return result
94. Binary Tree Inorder Traversal
Explanation
- Recursive
- Iterative
- Morris Traversal
Interactive Visualization
Analysis
- Python
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node):
if not node:
return
dfs(node.left)
result.append(node.val)
dfs(node.right)
result = []
dfs(root)
return result
Interactive Visualization
Analysis
- Python
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = collections.deque([(root, False)])
result = []
while stack:
node, visited = stack.pop()
if node:
if visited:
result.append(node.val)
else:
stack.append((node.right, False))
stack.append((node, True))
stack.append((node.left, False))
return result
Interactive Visualization
Analysis
- Python
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
current = root
while current:
if not current.left:
result.append(current.val)
current = current.right
else:
# Find inorder predecessor
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
predecessor.right = current
current = current.left
else:
result.append(current.val)
predecessor.right = None
current = current.right
return result
145. Binary Tree Postorder Traversal
Explanation
- Recursive
- Iterative
- Morris Traversal
Interactive Visualization
Analysis
- Python
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
result.append(node.val)
result = []
dfs(root)
return result
Interactive Visualization
Analysis
- Python
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = collections.deque([(root, False)])
result = []
while stack:
node, visited = stack.pop()
if node:
if visited:
result.append(node.val)
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return result
Interactive Visualization
Analysis
- Python
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
current = root
result = []
while current:
if not current.right:
result.append(current.val)
current = current.left
else:
predecessor = current.right
while predecessor.left and predecessor.left != current:
predecessor = predecessor.left
if predecessor.left is None:
result.append(current.val)
predecessor.left = current
current = current.right
else:
predecessor.left = None
current = current.left
return result[::-1]
Breadth First Search
102. Binary Tree Level Order Traversal
Explanation
- BFS (Queue)
- DFS (Recursive)
- DFS (Iterative)
- DFS (Morris)
Interactive Visualization
Analysis
- Python
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = []
queue = collections.deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
if node:
level.append(node.val)
queue.append(node.left)
queue.append(node.right)
if level:
levels.append(level)
return levels
Interactive Visualization
Analysis
- Python
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def dfs(node, level):
if not node:
return
if level == len(levels):
levels.append([])
levels[level].append(node.val)
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = []
dfs(root, 0)
return levels
Interactive Visualization
Analysis
- Python
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = []
stack = [(root, False, 0)]
while stack:
node, visited, level = stack.pop()
if node:
if visited:
if len(levels) == level:
levels.append([])
levels[level].append(node.val)
else:
stack.append((node.right, False, level + 1))
stack.append((node.left, False, level + 1))
stack.append((node, True, level))
return levels
Explanation
Analysis
- Python
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = []
current = root
level = 0
append_new_level = lambda level: levels.append([]) if level == len(levels) else None
while current:
if not current.left:
append_new_level(level)
levels[level].append(current.val)
current = current.right
level += 1
else:
diff = 0
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
diff += 1
if predecessor.right is None:
append_new_level(level)
levels[level].append(current.val)
predecessor.right = current
current = current.left
level += 1
else:
predecessor.right = None
current = current.right
level -= diff + 1
return levels
107. Binary Tree Level Order Traversal II
- BFS (Queue)
- DFS (Recursive)
- DFS (Iterative)
- DFS (Morris)
Interactive Visualization
Analysis
- Python
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = collections.deque()
queue = collections.deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
if node:
level.append(node.val)
queue.append(node.left)
queue.append(node.right)
if level:
levels.appendleft(level)
return list(levels)
Interactive Visualization
Analysis
- Python
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
def dfs(node, level):
if not node:
return
if level == len(levels):
levels.appendleft([])
levels[len(levels) - level - 1].append(node.val)
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = collections.deque()
dfs(root, 0)
return list(levels)
Interactive Visualization
Analysis
- Python
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = collections.deque()
stack = [(root, False, 0)]
while stack:
node, visited, level = stack.pop()
if node:
if visited:
levels[len(levels) - level - 1].append(node.val)
else:
if level == len(levels):
levels.appendleft([])
stack.append((node.right, False, level + 1))
stack.append((node.left, False, level + 1))
stack.append((node, True, level))
return list(levels)
Analysis
- Python
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = collections.deque()
current = root
level = 0
append_new_level = lambda level: (
levels.appendleft([]) if level == len(levels) else None
)
while current:
if not current.left:
append_new_level(level)
levels[len(levels) - level - 1].append(current.val)
current = current.right
level += 1
else:
predecessor = current.left
diff = 0
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
diff += 1
if predecessor.right is None:
append_new_level(level)
levels[len(levels) - level - 1].append(current.val)
predecessor.right = current
current = current.left
level += 1
else:
predecessor.right = None
current = current.right
level -= diff + 1
return list(levels)
103. Binary Tree Zigzag Level Order Traversal
- BFS (Queue)
- DFS (Recursive)
- DFS (Iterative)
- DFS (Morris)
Analysis
- Python
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
queue = collections.deque([root])
result = []
level_number = 0
while queue:
level = collections.deque()
for _ in range(len(queue)):
node = queue.popleft()
if node:
if level_number % 2 == 0:
level.append(node.val)
else:
level.appendleft(node.val)
queue.append(node.left)
queue.append(node.right)
if level:
result.append(list(level))
level_number += 1
return result
Analysis
- Python
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def dfs(node, level):
if not node:
return
if level == len(levels):
levels.append(collections.deque())
if level % 2 == 0:
levels[level].append(node.val)
else:
levels[level].appendleft(node.val)
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = []
dfs(root, 0)
return [list(i) for i in levels]
Analysis
- Python
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = []
stack = [(root, False, 0)]
while stack:
node, visited, level = stack.pop()
if node:
if visited:
if level % 2 == 0:
levels[level].append(node.val)
else:
levels[level].appendleft(node.val)
else:
if len(levels) == level:
levels.append(collections.deque())
stack.append((node.right, False, level + 1))
stack.append((node.left, False, level + 1))
stack.append((node, True, level))
return [list(i) for i in levels]
Analysis
- Python
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = []
current = root
level = 0
append_new_level = lambda level: (
levels.append(collections.deque()) if len(levels) == level else None
)
insert = lambda val: (
levels[level].append(val) if level % 2 == 0 else levels[level].appendleft(val)
)
while current:
if not current.left:
append_new_level(level)
insert(current.val)
current = current.right
level += 1
else:
predecessor = current.left
diff = 0
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
diff += 1
if predecessor.right is None:
append_new_level(level)
insert(current.val)
predecessor.right = current
current = current.left
level += 1
else:
predecessor.right = None
current = current.right
level -= diff + 1
return [list(i) for i in levels]
Vertical Order Traversal
314. Binary Tree Vertical Order Traversal
Explanation
- BFS (Queue)
- DFS (Recursive)
Analysis
- Python
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
queue = collections.deque([(root, 0)])
columns = collections.defaultdict(list)
min_col, max_col = 1000, -1000
while queue:
for _ in range(len(queue)):
node, col = queue.popleft()
if node:
min_col, max_col = min(col, min_col), max(col, max_col)
columns[col].append(node.val)
queue.append((node.left, col - 1))
queue.append((node.right, col + 1))
return [columns[col] for col in range(min_col, max_col + 1)]
Analysis
- Python
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def dfs(node, row, col):
nonlocal min_col, max_col
if node:
min_col, max_col = min(col, min_col), max(col, max_col)
columns[col].append((row, node.val))
dfs(node.left, row + 1, col - 1)
dfs(node.right, row + 1, col + 1)
min_col, max_col = 1000, -1000
columns = collections.defaultdict(list)
dfs(root, 0, 0)
result = []
for col in range(min_col, max_col + 1):
result.append(
[node_val for row, node_val in sorted(columns[col], key=lambda x: x[0])]
)
return result
987. Vertical Order Traversal of a Binary Tree
- BFS (Queue)
- DFS (Recursive)
Analysis
- Python
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
queue = collections.deque([(root, 0, 0)])
columns = collections.defaultdict(list)
min_col, max_col = 1000, -1000
while queue:
for _ in range(len(queue)):
node, row, col = queue.popleft()
if node:
min_col, max_col = min(col, min_col), max(col, max_col)
columns[col].append((row, node.val))
queue.append((node.left, row + 1, col - 1))
queue.append((node.right, row + 1, col + 1))
result = []
for col in range(min_col, max_col + 1):
result.append([node_val for row, node_val in sorted(columns[col])])
return result
Analysis
- Python
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
def dfs(node, row, col):
nonlocal min_col, max_col
if node:
min_col, max_col = min(col, min_col), max(col, max_col)
columns[col].append((row, node.val))
dfs(node.left, row + 1, col - 1)
dfs(node.right, row + 1, col + 1)
min_col, max_col = 1000, -1000
columns = collections.defaultdict(list)
dfs(root, 0, 0)
result = []
for col in range(min_col, max_col + 1):
result.append([node_val for row, node_val in sorted(columns[col])])
return result