Tree DFS
Overview
Depth-First Search (DFS) on a Binary Tree traverses by going as deep as possible down a single path before retreating (backtracking) to explore a different path.
While BFS uses a Queue (FIFO) to explore broadly, DFS fundamentally relies on a Stack (LIFO) to dive deep. Because the JVM itself operates using a Call Stack, Tree DFS is almost universally written using Recursion, resulting in incredibly elegant, 3-line algorithms that leverage the compiler to manage the stack for you.
DFS is the algorithmic tool of choice when you need to inspect complete paths from root to leaves, or when you are searching for a node that you strongly suspect is located deep at the bottom of the tree. Furthermore, it is significantly more memory-efficient than BFS for wide, bushy trees, requiring only O(H) space, where H is the height of the tree (which is just O(log N) in a balanced tree, compared to BFS's O(N)).
Syntax
public class TreeDFS {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
// A fundamental recursive DFS template
public void dfs(TreeNode root) {
// 1. Base Case: Reached the bottom or an empty tree
if (root == null) {
return;
}
// 2. Process current node (Pre-Order logic goes here)
System.out.println("Visiting: " + root.val);
// 3. Recurse deep down the left side
dfs(root.left);
// 4. Recurse deep down the right side
dfs(root.right);
}
// DFS is perfect for calculating Tree Height recursively
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}Common Pitfalls
- StackOverflowError on 'Degenerate' trees. A degenerate tree is a tree where every node only has one child, effectively forming a straight Linked List. If this list has 50,000 nodes, a recursive DFS will push 50,000 frames to the JVM Call Stack and crash. Iterative DFS (using
java.util.Stack) is required for massive unbalanced trees in production. - Returning values prematurely. In algorithms searching for a specific node, beginners often write
dfs(node.left); return true;. This skips checking the right side entirely! You must capture the result:boolean foundLeft = dfs(node.left); if (foundLeft) return true;. - Using Global variables to store state. Storing results in a class-level variable
int count = 0;works in single LeetCode test cases but fails catastrophically in multi-threaded production servers. Always pass state down via method arguments or return it up the recursive chain.
Interview Questions
The space complexity is determined by the maximum depth of the call stack, which equals the Height of the tree: O(H). In a perfectly balanced tree, this is O(log N). In a completely unbalanced tree, it degrades to O(N).
By explicitly managing your own java.util.ArrayDeque acting as a Stack. You push the root. In a while loop, you pop a node, process it, and then explicitly push its right child first, followed by its left child (so the left child is at the top of the stack and gets popped and processed first).
Real-World Example
Compilers evaluating Abstract Syntax Trees (AST). When you write (5 + 3) * 2 in code, the compiler parses this and builds a tree where * is the root, + is the left child, and 2 is the right. The compiler evaluates this using a post-order DFS: it must go as deep as possible to evaluate (5 + 3) before it can return that value up to perform the multiplication.
class ASTNode {
String value;
ASTNode left, right;
boolean isLeaf() { return left == null && right == null; }
}
public class CompilerAST {
// Evaluating a math expression tree using DFS
public int evaluate(ASTNode node) {
if (node.isLeaf()) {
return Integer.parseInt(node.value);
}
// Deep DFS to get evaluated child values FIRST
int leftVal = evaluate(node.left);
int rightVal = evaluate(node.right);
// Then process the current node based on the operator
if (node.value.equals("+")) return leftVal + rightVal;
if (node.value.equals("*")) return leftVal * rightVal;
if (node.value.equals("-")) return leftVal - rightVal;
return 0;
}
}Check Your Knowledge
Test your understanding of Tree DFS with these quick questions.