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

Easy3 solutionsexplanationanalysis3 playgrounds

Preorder Traversal

B

Preorder traversal (Iterative)

M

Tree: Preorder Traversal

E

---

144. Binary Tree Preorder Traversal

Explanation

Solutions:

Interactive Visualization

Analysis

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

Easy3 solutionsexplanationanalysis3 playgrounds

Inorder Traversal

E

Iterative Inorder

M

Tree: Inorder Traversal

E

---

94. Binary Tree Inorder Traversal

Explanation

Solutions:

Interactive Visualization

Analysis

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

Easy3 solutionsexplanationanalysis3 playgrounds

Postorder Traversal

B

Iterative Postorder

M

Tree: Postorder Traversal

E

---

145. Binary Tree Postorder Traversal

Explanation

Solutions:

Interactive Visualization

Analysis

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

---

Breadth First Search

102. Binary Tree Level Order Traversal

Medium4 solutionsexplanationanalysis4 playgrounds

Level order traversal

E

Level Order Line by Line

E

Tree: Level Order Traversal

E

---

102. Binary Tree Level Order Traversal

Explanation

Solutions:

Interactive Visualization

Analysis

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

Medium4 solutionsanalysis4 playgrounds

Reverse Level Order Traversal

E

---

107. Binary Tree Level Order Traversal II

Solutions:

Interactive Visualization

Analysis

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

Medium4 solutionsanalysis4 playgrounds

ZigZag Tree Traversal

M

Level Order in spiral form

E

---

103. Binary Tree Zigzag Level Order Traversal

Solutions:

Interactive Visualization

Analysis

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

Medium2 solutionsexplanationanalysis2 playgrounds

Vertical Tree Traversal

M

---

314. Binary Tree Vertical Order Traversal

Explanation

Solutions:

Interactive Visualization

Analysis

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

Hard2 solutionsanalysis2 playgrounds

---

987. Vertical Order Traversal of a Binary Tree

Solutions:

Interactive Visualization

Analysis

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

---