Depth-First Search Fundamentals

Depth-First Search (DFS) is a fundamental traversal algorithm used to explore tree or graph structures. As the name implies, DFS explores as deep as possible along each branch before backtracking to explore other unvisited branches. In a binary tree, this means visiting a node, recursively exploring its entire left subtree, and then recursively exploring its entire right subtree.

Because DFS matches the LIFO (Last-In, First-Out) nature of function calls, it can be implemented elegantly using recursion (the system call stack).

The Core Concept: Maximum Depth of a Binary Tree

To understand this concept deeply, let's explore Maximum Depth of Binary Tree.

Problem Statement: Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

The DFS Breakthrough — $O(N)$ Time & $O(H)$ Space

Instead of tracking nodes level by level, DFS computes the maximum depth bottom-up using a simple recurrence relation: $ext{MaxDepth}( ext{node}) = 1 + max( ext{MaxDepth}( ext{node.left}), ext{MaxDepth}( ext{node.right}))$

As the recursion executes:

Base Case: If a node is None (empty), its depth is 0.
Recursive Calls: We recursively calculate the maximum depth of the left subtree and the right subtree.
Aggregation: We take the maximum of these two depths and add 1 (representing the current node) to get the depth at the current level.

This recursive relation computes the depth of the entire tree in a single pass.

Step-by-Step Traversal

Let's trace the algorithm on the binary tree: [3, 9, 20, None, None, 15, 7].

Step 1: Initialization

The DFS recursion begins. We start by calling max_depth on the root node (Node 3).

INITMaximum Depth of Binary Tree (DFS)1 / 7

scroll to zoom · drag to pan

Step 2: Visit Root Node

We visit Node 3. To find its depth, we must query its left and right subtrees.

VISITAt node 3, depth=11 / 6

scroll to zoom · drag to pan

Step 3: Explore Left Subtree

DFS moves to the left child, Node 9.
Since Node 9 is a leaf (both left and right children are None), its recursive calls return 0.

VISITAt node 9, depth=21 / 5

scroll to zoom · drag to pan

Node 9 returns depth 1 + max(0, 0) = 1 to the root.

Step 4: Explore Right Subtree

DFS returns to Node 3 and then calls max_depth on the right child, Node 20.

VISITAt node 20, depth=21 / 4

scroll to zoom · drag to pan

To find Node 20's depth, DFS must query its children. It moves to Node 15.
Since Node 15 is a leaf, its recursive calls return 0, and Node 15 returns depth 1 to Node 20.

VISITAt node 15, depth=31 / 3

scroll to zoom · drag to pan

DFS backtracks to Node 20 and moves to the right child, Node 7.
Since Node 7 is a leaf, its recursive calls return 0, and Node 7 returns depth 1 to Node 20.

VISITAt node 7, depth=31 / 2

scroll to zoom · drag to pan

Node 20 combines these results: 1 + max(1, 1) = 2 and returns depth 2 to the root.

Step 5: Final Result

At the root Node 3, we combine the results from the left subtree (depth 1) and right subtree (depth 2): $ext{Depth} = 1 + max(1, 2) = 3$ The maximum depth of the tree is 3.

DONEMaximum depth = 3 ✓1 / 1

scroll to zoom · drag to pan

Code Implementation

def maxDepth(root: TreeNode | None) -> int:
    # Base Case: an empty node has depth 0
    if root is None:
        return 0
        
    # Recursive calls to find the depth of left and right subtrees
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    
    # The depth of the current node is 1 plus the maximum of its subtrees
    return 1 + max(left_depth, right_depth)

Time Complexity: $O(N)$ — where $N$ is the total number of nodes, as we visit each node exactly once. Space Complexity: $O(H)$ — where $H$ is the height of the tree, representing the recursion stack depth. In the worst case (skewed tree), $H = N$ ; in the best case (balanced tree), $H = log_2 N$ .

Tree Traversal Orders

DFS can traverse tree nodes in three distinct orders:

1. In-Order Traversal (Left → Root → Right)

Visits the left subtree, then the root, then the right subtree. In a Binary Search Tree (BST), this visits nodes in sorted ascending order.

def inorder(node):
    if not node: return
    inorder(node.left)
    visit(node)
    inorder(node.right)

2. Pre-Order Traversal (Root → Left → Right)

Visits the root first, then the left subtree, then the right subtree. Useful for copying trees or serializing structure.

def preorder(node):
    if not node: return
    visit(node)
    preorder(node.left)
    preorder(node.right)

3. Post-Order Traversal (Left → Right → Root)

Visits children first, then the root. Useful for bottom-up calculations (like deleting a tree or calculating node heights).

def postorder(node):
    if not node: return
    postorder(node.left)
    postorder(node.right)
    visit(node)

When Do I Use This?

Reach for DFS when:

The problem involves hierarchical structures like binary trees, N-ary trees, graphs, or matrix grids.
You need to search for paths, calculate subtree heights, validate properties bottom-up, or explore all possible choices (backtracking).
The solution depends on aggregating values from child subtrees before returning a result to the parent.

If these apply, DFS recursion is the standard approach.

Practice Problems

Done	Question	Difficulty
	Maximum Depth of Binary Tree	Easy
	Validate Binary Search Tree	Medium
	Invert Binary Tree	Easy
	Diameter of a Binary Tree	Easy
	Balanced Binary Tree	Easy

Depth-First Search Fundamentals

The Core Concept: Maximum Depth of a Binary Tree

The DFS Breakthrough — O(N)O(N)O(N) Time & O(H)O(H)O(H) Space

Step-by-Step Traversal

Step 1: Initialization

Step 2: Visit Root Node

Step 3: Explore Left Subtree

Step 4: Explore Right Subtree

Step 5: Final Result

Code Implementation

Tree Traversal Orders

1. In-Order Traversal (Left → Root → Right)

2. Pre-Order Traversal (Root → Left → Right)

3. Post-Order Traversal (Left → Right → Root)

When Do I Use This?

Practice Problems

Comments

The DFS Breakthrough — $O(N)$ Time & $O(H)$ Space