Skip to main content

Tree Traversal

Tree traversal is the process of visiting each node in a tree data structure exactly once in a systematic way.

144. Binary Tree Preorder Traversal​

Explanation

Solutions:
Visualize
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

94. Binary Tree Inorder Traversal​

Explanation

Solutions:
Visualize
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

145. Binary Tree Postorder Traversal​

Explanation

Solutions:
Visualize
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

606. Construct String from Binary Tree​

Medium·

Explanation

Solutions:
Visualize
def tree2str(self, root: Optional[TreeNode]) -> str:
def recursion(node):
if node:
left_subtree = recursion(node.left) or []
right_subtree = recursion(node.right) or []
if left_subtree:
left_subtree = ["("] + left_subtree + [")"]
if right_subtree:
right_subtree = ["("] + right_subtree + [")"]
if not left_subtree and right_subtree:
left_subtree = ["()"]
return [str(node.val)] + left_subtree + right_subtree
 
ans = recursion(root)
return "".join(ans)

102. Binary Tree Level Order Traversal​

Explanation

Solutions:
Visualize
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) if node.left else None
queue.append(node.right) if node.right else None
if level:
levels.append(level)
return levels

107. Binary Tree Level Order Traversal II​

Medium·
Solutions:
Visualize
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) if node.left else None
queue.append(node.right) if node.right else None
if level:
levels.appendleft(level)
return list(levels)

103. Binary Tree Zigzag Level Order Traversal​

Solutions:
Visualize
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) if node.left else None
queue.append(node.right) if node.right else None
if level:
result.append(list(level))
level_number += 1
return result

Vertical Order Traversal​

314. Binary Tree Vertical Order Traversal​

Medium·

Explanation

Solutions:
Visualize
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)) if node.left else None
queue.append((node.right, col + 1)) if node.right else None
 
return [columns[col] for col in range(min_col, max_col + 1)]

987. Vertical Order Traversal of a Binary Tree​

Hard·
Solutions:
Visualize
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)) if node.left else None
queue.append((node.right, row + 1, col + 1)) if node.right else None
 
result = []
for col in range(min_col, max_col + 1):
result.append([node_val for row, node_val in sorted(columns[col])])
return result