Depth-First Search

Tags

Depth-First Search

Category

Graphs

Difficulty

Easy

Problem Statement

Given a graph represented as a tree of nodes where each node has a name and a list of children, implement a depth-first search method that traverses the graph and returns an array of all node names in DFS order.

Intuition

Depth-first search explores as far as possible along each branch before backtracking. Starting from a node, we visit it, then recursively visit each of its children in order. This naturally produces a traversal that goes deep before going wide.

Approach

  1. Start at the root node. Add its name to the result array.
  2. For each child of the current node (in order):
    • Recursively perform DFS on that child, passing the same result array.
  3. Return the result array.

Pseudocode

class Node:
    name
    children

    function depthFirstSearch(results):
        results.append(self.name)
        for child in self.children:
            child.depthFirstSearch(results)
        return results

Time & Space Complexity

  • Time: O(v + e) where v is the number of vertices (nodes) and e is the number of edges. Each node and edge is visited once.
  • Space: O(v) — the result array stores all v node names, and the recursion stack can go as deep as v in the worst case.

Key Insights

  • DFS is naturally implemented with recursion (which uses the call stack) or explicitly with a stack data structure.
  • The traversal order depends on the order of children — left-to-right if children are ordered.
  • DFS uses less memory than BFS for wide, shallow graphs but more memory for narrow, deep graphs.
  • For trees (acyclic connected graphs), no "visited" set is needed. For general graphs with cycles, a visited set prevents infinite loops.

Edge Cases

  • A single node with no children: return an array with just that node's name.
  • A node with many children but no grandchildren (flat tree): all children are visited in order.
  • A deeply nested chain (like a linked list): recursion depth equals the number of nodes — risk of stack overflow for very deep graphs.
  • Empty graph / null root: return an empty array.

Linked mentions