Tree Traversals

DFS vs BFS, the two ways to visit every node in a tree

Tree traversal visits every node exactly once. Two fundamental strategies:
DFS (Depth-First Search): Go deep before going wide. Three orders:

Pre-order: Root → Left → Right (copy tree structure)

In-order: Left → Root → Right (sorted order for BST)

Post-order: Left → Right → Root (delete tree, calc sizes)

BFS (Breadth-First Search): Level by level using a queue.

All traversals implementedpython

from collections import deque

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val; self.left = left; self.right = right

def preorder(root):   # Root, Left, Right
    if not root: return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):    # Left, Root, Right
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):  # Left, Right, Root
    if not root: return []
    return postorder(root.left) + postorder(root.right) + [root.val]

def bfs(root):        # Level by level
    if not root: return []
    queue, result = deque([root]), []
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder(root))   # [1, 2, 4, 5, 3]
print(inorder(root))    # [4, 2, 5, 1, 3]
print(postorder(root))  # [4, 5, 2, 3, 1]
print(bfs(root))        # [1, 2, 3, 4, 5]

🤔Quick Check

You need to find the shortest path from root to a specific node. Which traversal?

🎯

Phase Complete!

Trees

Binary trees, BSTs, and traversals, you're thinking hierarchically now. Graphs generalize trees further, let's explore them next.

0/500

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Level Order Return

Return the level-order traversal as a list of lists (each level is a separate list).
Expected output: [[3], [9, 20], [15, 7]]

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next