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​

Preorder traversal visits nodes in the order: Root → Left → Right. This means we process the current node first, then recursively traverse the left subtree, followed by the right subtree.

3 Approaches
FIG. BINARY TREE PREORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
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​

Inorder traversal visits nodes in the order: Left → Root → Right. For binary search trees, this produces values in ascending sorted order.

3 Approaches
FIG. BINARY TREE INORDER TRAVERSAL RECURSIVE● INTERACTIVE
visualization loads as you reach it
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​

Postorder traversal visits nodes in the order: Left → Right → Root. This is useful when you need to process children before their parent (e.g., deleting nodes, calculating directory sizes).

3 Approaches
FIG. BINARY TREE POSTORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
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·

Serialize the tree in preorder with parentheses around each child subtree. The only subtlety: a node with a right child but no left child must still emit an empty () for the missing left, so the structure is unambiguous. Empty parentheses are otherwise omitted.

2 Approaches
FIG. CONSTRUCT STRING FROM BINARY TREE● INTERACTIVE
visualization loads as you reach it
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​

Level order traversal visits nodes level by level from top to bottom, left to right. This is also known as Breadth-First Search (BFS) for trees.

4 Approaches
FIG. BINARY TREE LEVEL ORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
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·
4 Approaches
FIG. BINARY TREE LEVEL ORDER TRAVERSAL II● INTERACTIVE
visualization loads as you reach it
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​

4 Approaches
FIG. BINARY TREE ZIGZAG LEVEL ORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
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·

Vertical order traversal groups nodes by their horizontal distance from the root. Root is at column 0, left children decrease column by 1, right children increase column by 1. Within each column, nodes appear from top to bottom.

2 Approaches
FIG. BINARY TREE VERTICAL ORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
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·
2 Approaches
FIG. VERTICAL ORDER TRAVERSAL OF A BINARY TRE● INTERACTIVE
visualization loads as you reach it
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