Tree DFS

Overview

Depth-First Search (DFS) on a tree dives as deeply as possible down one branch before backing up and exploring the next. Because trees are naturally recursive structures, DFS is almost always implemented recursively, making the code incredibly short and elegant.

Syntax

The call stack implicitly acts as our 'memory'. It handles tracking where we are and backtracking for us.

Basic Recursive DFS

java

public void dfs(TreeNode root) {
    if (root == null) return; // Base case
    
    System.out.println(root.val); // Process node
    dfs(root.left);               // Dive left
    dfs(root.right);              // Dive right
}

Common Pitfalls

Stack Overflow on massive, unbalanced trees. A tree with 100,000 nodes in a straight line will cause 100,000 recursive calls, crashing the JVM.

Interview Tips

Tree DFS is implicitly implemented using the Call Stack via Recursion.

Real-World Example

DFS is used to search for files on a computer hard drive. It dives into folder A, then subfolder B, all the way down, before coming back up to check folder C.

example

java

// The file deletion example shown in Recursion is an exact Tree DFS!

Take Java Quiz