Tree Traversals

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

You have a tree full of nodes. Sometimes you need to touch every single one, once. To read them, to add them up, to print them. That is called walking the tree, or its posh name, a traversal.
There is more than one way to walk it, and the only thing that changes is the order you visit the nodes in. Tap the four walks below and watch each one light up the tree in its own order.

The first three walks all dive down one branch before trying another. That "go deep first" style has a name: DFS, depth-first. They only differ in *when* you stop to look at each node, before its two sides, between them, or after both.

Pre-order: look at the node first, then its left side, then its right.

In-order: left side first, then the node, then the right. On a sorted tree this hands the values back in order, which is a genuinely useful trick.

Post-order: both sides first, then the node last.

The fourth walk is different. It goes row by row from the top instead of diving down. That "go wide first" style is called BFS, breadth-first, and it is the one you reach for when you want the shortest path to something.

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