What is Depth-First Search (DFS)?

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (or some arbitrary node) and explores as far as possible along each branch before backtracking.

How is DFS typically implemented?

DFS is often implemented using recursion, which uses the call stack to keep track of the nodes to visit. It can also be implemented iteratively using an explicit stack data structure.

Graph Traversal

Depth-First Search (DFS) Problems

Master DFS for your coding interviews. This guide covers common problems, recursive and iterative solutions, and AI-powered hints to help you excel in graph and tree traversal questions.

Recursive In-order Traversal of a Binary Tree

DFS is naturally recursive. A classic example is the in-order traversal of a binary tree, where we visit the left subtree, then the root, then the right subtree.

                            function inOrderTraversal(root) {
                            const result = [];
                            
                            function traverse(node) {
                            if (!node) return;
                            
                            traverse(node.left);
                            result.push(node.val);
                            traverse(node.right);
                            }
                            
                            traverse(root);
                            return result;
                            }
                        

AI Coach Hint: The elegance of DFS lies in its recursive simplicity. However, be mindful of the call stack depth, as a very deep recursion can lead to a stack overflow error. For very large or deep graphs/trees, an iterative approach with an explicit stack might be safer.