DFS (Depth-First Search) in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#include <stdlib.h>
typedef struct N { int d; struct N *l, *r; } N;
N* n(int d) { N* t = malloc(sizeof(N)); t->d = d; t->l = t->r = NULL; return t; }
void dfs(N* r) {
    if (!r) return;
    printf("%d ", r->d);
    dfs(r->l);
    dfs(r->r);
}
int main() {
    N* r = n(1);
    r->l = n(2); r->r = n(3);
    r->l->r = n(4);
    dfs(r);
}

C Output

Input:  
      1
     / \
    2   3
     \
      4

Output:  
Input: 1 2 4 3
Output: 1 2 4 3

C++ Program

#include <iostream>
using namespace std;
struct N {
    int d; N *l, *r;
    N(int v): d(v), l(0), r(0) {}
};
void dfs(N* r) {
    if (!r) return;
    cout << r->d << " ";
    dfs(r->l);
    dfs(r->r);
}
int main() {
    N* r = new N(10);
    r->l = new N(5); r->r = new N(15);
    r->r->l = new N(12);
    dfs(r);
}

C++ Output

Input:  
       10
      /  \
     5    15
          /
         12

Output:  
Input: 10 5 15 12
Output: 10 5 15 12

JAVA Program

class N {
    int d; N l, r;
    N(int d) { this.d = d; }
}
public class Main {
    static void dfs(N r) {
        if (r == null) return;
        System.out.print(r.d + " ");
        dfs(r.l);
        dfs(r.r);
    }
    public static void main(String[] a) {
        N r = new N(6);
        r.l = new N(4); r.r = new N(8);
        r.l.l = new N(2);
        dfs(r);
    }
}

JAVA Output

Input:  
        6
       / \
      4   8
     /
    2  

Output:  
Input: 6 4 2 8
Output: 6 4 2 8

Python Program

class N:
    def __init__(s, d): s.d, s.l, s.r = d, None, None
def dfs(r):
    if r: print(r.d, end=' '); dfs(r.l); dfs(r.r)

r = N(7)
r.l = N(3); r.r = N(9)
r.r.r = N(11)
dfs(r)

Python Output

Input:  
      7
     / \
    3   9
           \
           11 

Output:  
Input: 7 3 9 11
Output: 7 3 9 11

In-Depth Explanation

Example

DFS (Preorder) = going to a node before the children:

Visit root

Go left (completely), then right

Thus in the Java tree:

    6

   / \

  4   8

 /

2

The DFS preorder sequence is: 6 4 2 8

Real-Life Analogy

Think of looking through a directory on your computer. You open a directory, enter its subdirectory, and continue going deeper until you reach a dead end — then you turn back. That's Depth-First — you go as deep as you can before working on siblings.

Such as navigating a maze by always turning left until you reach a wall, then turn back and try the right.

Why It Matters

DFS is central to:

Tree-based algorithms

Pathfinding (game maps, maze solvers)

Evaluating expressions (expression trees)

Traversing XML/HTML (DOM tree)

It's more space-efficient than BFS in most cases (uses stack space, not a queue).

Learning Insights

This illustrates:

Clean recursion with base and recursive cases

How tree traversal works

Depth-first strategies — crucial for graphs, trees, AI, compilers, and more

DFS has 3 varieties: preorder (root-left-right), inorder (left-root-right), and postorder (left-right-root). Preorder is employed here, suitable for copying or evaluating trees top-down.

Interview & Real-World Use

DFS is frequently interviewed:

To verify recursion basics

To check tree traversal variations

As a foundation to solve more challenging graph problems

Real-world applications:

Browsing file systems (folder → subfolder)

Evaluating expressions (ASTs)

Parsing nested data structures (HTML, XML, JSON)

Solving puzzles in AI (e.g., Sudoku, 8-Queens)

Depth-First Search is one of the most critical traversal algorithms in computer science. It shows you how to think recursively, how to go deep into structured data, and how to traverse trees and graphs in an efficient manner. The tidy C, C++, Java, and Python codes below show DFS applying preorder logic to various real input trees. Learning DFS improves your core in data structures, recursion, and problem-solving — skills that are exercised in interviews and crucial in real-world applications such as compilers, AI, and game development.