Welcome to the first lesson of our module on Graphs and Trees. In our last session, we used backtrackingāa form of Depth-First Searchāto explore an implicit decision tree for generating subsets. Today, we will apply that same "go deep" principle to explicit tree data structures, a cornerstone of many software systems and technical interviews.
This lesson is dedicated to mastering Depth-First Search (DFS). You will learn to implement it both recursively and iteratively, understanding the trade-offs between these approaches. We will then apply DFS to solve two common categories of interview problems: pathfinding and tree validation. This will solidify your grasp of a fundamental traversal algorithm that is essential for your goal of tackling complex system design and algorithmic challenges.
1. The Essence of Depth-First Search
Depth-First Search is a traversal algorithm that starts at the root and explores as far as possible along each branch before backtracking. Imagine navigating a maze by always taking the leftmost path until you hit a dead end, then backing up to the last junction and trying the next available path. That's the core intuition of DFS.
For a binary tree, this "go deep" strategy can be implemented in three distinct orders, depending on when you "visit" (or process) the current node relative to its children:
- Pre-order Traversal: Visit the current node, then traverse the left subtree, then traverse the right subtree.
(Root, Left, Right). This is useful for tasks like creating a copy of the tree. - In-order Traversal: Traverse the left subtree, then visit the current node, then traverse the right subtree.
(Left, Root, Right). For a Binary Search Tree (BST), this visits nodes in ascending order. - Post-order Traversal: Traverse the left subtree, then traverse the right subtree, then visit the current node.
(Left, Right, Root). This is useful for tasks like deleting a tree, as you process children before their parent.
The image below illustrates the path taken for each traversal order on the same tree. The position of the red dot relative to the node indicates when the node is "visited".
2. Recursive vs. Iterative Implementation
Since trees are inherently recursive structures, a recursive DFS implementation is often the most straightforward and elegant. The function calls itself on the child nodes, and the language's call stack naturally manages the state needed for backtracking.
However, a purely recursive approach can lead to a stack overflow error if the tree is very deep or heavily unbalanced. This is a practical concern for production systems. The solution is an iterative implementation using an explicit stack data structure to mimic the behavior of the recursive call stack.
The following article provides excellent Go implementations for both approaches. As you're proficient in Go, the code and explanations will be very accessible. We will focus on the Pre-order traversal pattern.
This FAUN.dev article by the_programmer() clearly breaks down how to implement and visualize both recursive and iterative DFS in Go.
First, read the recap section for a quick review of the core concept. Next, carefully study the recursive implementation. The step-by-step breakdown and the code snippet show how naturally recursion maps to the problem. The visual walkthrough of the call stack is particularly helpful. Then, move to the iterative implementation. Pay close attention to how a stack (a LIFO data structure) is used. Follow the logic in the iterative section where the author explains the algorithm and provides the Go code. Notice the crucial detail: the right child is pushed to the stack before the left child to ensure the left subtree is processed first. Finally, read the short analysis comparing the two methods.
For a JavaScript perspective, the article "Getting Started with Trees: Depth First Search(DFS)" provides clear code examples for both a recursive and iterative DFS, which you can review if you wish.
3. Application 1: Pathfinding Problems
DFS is perfectly suited for problems that involve finding a path, checking for a path's existence, or finding properties of a path. A classic interview question in this category is finding the maximum depth of a binary tree.
The recursive logic is beautifully simple: the maximum depth of a tree is 1 + max(max_depth(left_subtree), max_depth(right_subtree)). The base case is an empty tree, which has a depth of 0.
The following video from NeetCode walks through this problem, providing solutions for recursive DFS, iterative DFS, and BFS (which we will cover next).
Maximum Depth of Binary Tree - 3 Solutions - Leetcode 104 - Python
This video provides a clear walkthrough of three different solutions for finding the maximum depth of a binary tree.
Watch the introduction to understand the problem statement from the beginning. Pay close attention to the explanation of the recursive DFS solution. This is the most intuitive approach and directly models the problem's recursive nature. Next, watch the section on iterative DFS. This demonstrates how to solve the same problem with an explicit stack, storing pairs of (node, depth). This pattern is very powerful and avoids recursion limits.
4. Application 2: Validation Problems
Another common use of DFS is to validate whether a tree conforms to certain properties. The canonical example is "Validate Binary Search Tree." A BST has a specific ordering property: for any given node, all values in its left subtree must be smaller, and all values in its right subtree must be larger.
A common mistake is to only check a node against its immediate parent and children. This fails because the BST property must hold for all ancestors, not just the direct parent. For example, a node in the right subtree of a node N must not only be greater than N, but also greater than N's parent if N is in a right subtree.
The correct approach uses DFS to pass down min and max boundary constraints at each level of the recursion.
This NeetCode video explains the pitfall and the correct, elegant solution.
Validate Binary Search Tree - Depth First Search - Leetcode 98
This video covers LeetCode problem 98, "Validate Binary Search Tree," a classic validation problem.
First, watch the explanation of the BST property and the common but incorrect approach from the beginning. This highlights why a simple local check is insufficient. Next, focus on the core insight of the correct algorithm: using DFS with boundaries. The visualization of updating the left and right bounds as the traversal descends is key. Finally, walk through the code implementation, which translates this logic into a concise recursive helper function.
The textual resource "Getting Started with Trees" also covers this problem (98. Validate Binary Search Tree), and its JavaScript implementation provides a good reference to complement the video.
Conclusion
In this lesson, we established Depth-First Search as a fundamental tool for tree traversal. You learned how its "go deep" strategy can be implemented both recursively, for elegance, and iteratively, for safety against stack overflows.
Key Takeaways:
- Traversal Orders: DFS can be performed in Pre-order
(Root, Left, Right), In-order(Left, Root, Right), or Post-order(Left, Right, Root), each with different use cases. - Recursive vs. Iterative: The recursive approach is intuitive and uses the call stack implicitly. The iterative approach uses an explicit stack, offering protection against stack overflow in very deep trees.
- Pathfinding: DFS is excellent for problems involving path existence or properties. We saw this in finding a tree's maximum depth, where the solution is a recursive combination of the results from subproblems.
- Validation: DFS can validate tree-wide properties by passing constraints down through the traversal. We applied this by using
minandmaxboundaries to check for the Binary Search Tree property.
In our next lesson, we will explore the other major traversal algorithm: Breadth-First Search (BFS). Instead of going deep, BFS explores the tree level by level. We will see how this makes it the ideal choice for finding the shortest path in unweighted graphs and trees.