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 Approachesclick to switch
FIG. BINARY TREE PREORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each node exactly once.
Space
O(h)
  • The recursion call stack grows with tree height h.
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 Approachesclick to switch
FIG. BINARY TREE INORDER TRAVERSAL RECURSIVE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once.
Space
O(h)
  • The recursion call stack grows with tree height h (worst case O(n) for a skewed tree, O(log n) for a balanced one).
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 Approachesclick to switch
FIG. BINARY TREE POSTORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the tree's n nodes exactly once.
Space
O(h)
  • The recursion call stack grows with the tree's height h.
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 Approachesclick to switch
FIG. CONSTRUCT STRING FROM BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • recursion visits each of the n nodes exactly once, contributing its value and parentheses to the result list.
Space
O(h)
  • The recursion stack goes one frame deep per level, up to the tree height h.
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 Approachesclick to switch
FIG. BINARY TREE LEVEL ORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • The while queue loop dequeues every node exactly once via queue.popleft(), so the total work across all levels is a single O(n) pass, where n is the number of nodes.
Space
O(w)
  • queue holds at most one full level's worth of nodes at a time - in the worst case (the widest level of the tree) that is w nodes, where w is the tree's max width.
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 Approachesclick to switch
FIG. BINARY TREE LEVEL ORDER TRAVERSAL II● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Every node is dequeued and processed exactly once across all levels - n nodes total.
Space
O(w)
  • queue holds at most one full level at a time, so it grows to the tree's max width w.
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 Approachesclick to switch
FIG. BINARY TREE ZIGZAG LEVEL ORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each of the n nodes is popped from queue and appended to level exactly once, with O(1) deque operations for the zigzag insert.
Space
O(w)
  • queue holds at most one full level, bounded by the tree's max width w.
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 Approachesclick to switch
FIG. BINARY TREE VERTICAL ORDER TRAVERSAL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the number of nodes - the BFS visits every node exactly once, and level-order already delivers each column top-to-bottom, so no separate sort is needed.
Space
O(n)
  • columns stores every node's value, up to n entries total.
  • queue holds at most one full level's worth of nodes, which does not exceed n.
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 Approachesclick to switch
FIG. VERTICAL ORDER TRAVERSAL OF A BINARY TRE● INTERACTIVE
visualization loads as you reach it
Time
O(n + n log n)
  • The BFS visits every node once - O(n) - then sorted(columns[col]) runs per column; summed across all columns the elements sorted total n, so the worst case (all nodes sharing one column) costs O(n log n).
Space
O(sort + n)
  • columns stores every (row, val) pair, O(n); queue adds at most O(w), which never exceeds O(n).
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's sorted() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
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