Introduction

Tree Depth-First Search (DFS) is one of the most fundamental tree traversal patterns in computer science.

Instead of processing nodes level by level like BFS, DFS explores one branch completely before backtracking to explore another branch.

Tree DFS is heavily used in coding interviews because many tree problems naturally require recursion and divide-and-conquer thinking.

---

When Should You Use Tree DFS?

Use Tree DFS when the problem involves:

• Root-to-leaf paths
• Tree height
• Maximum depth
• Minimum depth (sometimes)
• Lowest Common Ancestor (LCA)
• Tree validation
• Path Sum
• Diameter of Tree
• Balanced Tree
• Binary Search Tree operations

Typical interview keywords:

• Path
• Recursive
• Height
• Depth
• Ancestor
• Leaf
• Backtracking
• Subtree

---

Basic Idea

Explore as deep as possible before returning.

graph TD
    Root["Root"] --> Left["Left"]
    Left["Left"] --> Left["Left"]
    Left["Left"] --> Leaf["Leaf"]
    Leaf["Leaf"] --> Backtrack["Backtrack"]
    Backtrack["Backtrack"] --> Right["Right"]
    Right["Right"] --> Repeat["Repeat"]

DFS naturally follows recursion.

---

Visualization

Example Tree

graph TD
    N_1_0_0["1"] --> N_2_1_1["2"]
    N_1_0_0["1"] --> N_3_1_2["3"]
    N_2_1_1["2"] --> N_4_2_1["4"]
    N_2_1_1["2"] --> N_5_2_2["5"]
    N_3_1_2["3"] --> N_6_2_3["6"]
    N_3_1_2["3"] --> N_7_2_4["7"]

DFS Traversal

graph TD
    N_1["1"] --> N_2["2"]
    N_2["2"] --> N_4["4"]
    N_4["4"] --> Back["Back"]
    Back["Back"] --> N_5["5"]
    N_5["5"] --> Back["Back"]
    Back["Back"] --> N_3["3"]
    N_3["3"] --> N_6["6"]
    N_6["6"] --> N_7["7"]

---

Three Types of DFS

1. Preorder

Visit

graph TD
    Root["Root"] --> Left["Left"]
    Left["Left"] --> Right["Right"]

Traversal

1 2 4 5 3 6 7

---

2. Inorder

Visit

graph TD
    Left["Left"] --> Root["Root"]
    Root["Root"] --> Right["Right"]

Traversal

4 2 5 1 6 3 7

For Binary Search Trees (BST), inorder traversal returns values in sorted order.

---

3. Postorder

Visit

graph TD
    Left["Left"] --> Right["Right"]
    Right["Right"] --> Root["Root"]

Traversal

4 5 2 6 7 3 1

---

DFS Decision Flow

graph TD
    Visit_Node["Visit Node"] --> Base_Case["Base Case?"]
    Base_Case["Base Case?"] --> Return["Return"]
    Return["Return"] --> Process_Node["Process Node"]
    Process_Node["Process Node"] --> DFS_Left["DFS Left"]
    DFS_Left["DFS Left"] --> DFS_Right["DFS Right"]
    DFS_Right["DFS Right"] --> Backtrack["Backtrack"]

---

Recursive Java Implementation

class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }

}

public class TreeDFS {

    public void preorder(TreeNode root) {

        if (root == null)
            return;

        System.out.print(root.val + " ");

        preorder(root.left);

        preorder(root.right);

    }

}

---

Inorder Traversal

public void inorder(TreeNode root) {

    if (root == null)
        return;

    inorder(root.left);

    System.out.print(root.val + " ");

    inorder(root.right);

}

---

Postorder Traversal

public void postorder(TreeNode root) {

    if (root == null)
        return;

    postorder(root.left);

    postorder(root.right);

    System.out.print(root.val + " ");

}

---

Iterative DFS Using Stack

Although recursion is the most common approach, DFS can also be implemented using a stack.

public List<Integer> preorderIterative(TreeNode root) {

    List<Integer> result = new ArrayList<>();

    if (root == null)
        return result;

    Stack<TreeNode> stack = new Stack<>();

    stack.push(root);

    while (!stack.isEmpty()) {

        TreeNode current = stack.pop();

        result.add(current.val);

        if (current.right != null)
            stack.push(current.right);

        if (current.left != null)
            stack.push(current.left);

    }

    return result;

}

---

Internal Working

Tree

graph TD
    N_1_0_0["1"] --> N_2_1_1["2"]
    N_1_0_0["1"] --> N_3_1_2["3"]
    N_2_1_1["2"] --> N_4_2_1["4"]
    N_2_1_1["2"] --> N_5_2_2["5"]

Recursive Calls

graph TD
    N_1["1"] --> N_2["2"]
    N_2["2"] --> N_4["4"]
    N_4["4"] --> NULL["NULL"]
    NULL["NULL"] --> Back["Back"]
    Back["Back"] --> N_5["5"]
    N_5["5"] --> Back["Back"]
    Back["Back"] --> N_3["3"]

Call Stack

graph TD
    N_1["1"] --> N_2["2"]
    N_2["2"] --> N_4["4"]
    N_4["4"] --> Return["Return"]
    Return["Return"] --> N_2["2"]
    N_2["2"] --> Return["Return"]
    Return["Return"] --> N_1["1"]

---

Recursion Tree

DFS(1)

├── DFS(2)

│   ├── DFS(4)

│   └── DFS(5)

└── DFS(3)

    ├── DFS(6)

    └── DFS(7)

---

Complexity Analysis

Let:

• n = Number of nodes
• h = Height of tree

Operation	Complexity
Time	O(n)
Recursive Space	O(h)
Iterative Space	O(h)

Each node is visited exactly once.

---

DFS vs BFS

Feature	DFS	BFS
Traversal	Depth First	Level First
Data Structure	Stack / Recursion	Queue
Best For	Paths, Height	Levels
Memory	O(h)	O(w)
Recursive	Yes	No

---

Common DFS Problems

Problem	Difficulty
Maximum Depth	Easy
Path Sum	Easy
Diameter of Binary Tree	Easy
Balanced Binary Tree	Easy
Lowest Common Ancestor	Medium
Binary Tree Paths	Easy
Validate BST	Medium
Maximum Path Sum	Hard
Serialize Binary Tree	Hard

---

Production Use Cases

File Systems

Traverse folders recursively.

---

XML / JSON Parsing

Process nested document structures.

---

Compiler Design

Traverse Abstract Syntax Trees (AST).

---

Database Query Optimizers

Traverse execution plans.

---

Web Crawlers

Explore links recursively.

---

AI Decision Trees

Evaluate branches of decision trees.

---

Cloud Infrastructure

Traverse dependency trees.

---

Version Control Systems

Walk commit trees and directory structures.

---

Common Mistakes

Missing Base Case

Always stop recursion.

if(root == null)
    return;

---

Choosing the Wrong Traversal

• Preorder → Copy / Serialize
• Inorder → BST Traversal
• Postorder → Delete / Evaluate

---

Stack Overflow

Very deep trees may exceed recursion limits.

Consider an iterative solution for extremely deep trees.

---

Modifying Nodes Incorrectly

Avoid changing tree links unless the problem explicitly requires it.

---

Ignoring Null Children

Always check child nodes before recursion or stack operations.

---

Interview Tips

Mention these observations:

• DFS explores one branch completely before backtracking.
• Recursion naturally fits tree traversal.
• Every recursive call creates a stack frame.
• Inorder traversal of a BST returns sorted values.
• DFS is ideal for path-related and subtree problems.

---

Frequently Asked Interview Questions

1. What is Tree DFS?

Answer

Tree DFS explores one branch of the tree as deeply as possible before backtracking to explore another branch.

---

2. What are the three DFS traversals?

Answer

• Preorder (Root → Left → Right)
• Inorder (Left → Root → Right)
• Postorder (Left → Right → Root)

---

3. What is the time complexity?

Answer

O(n) because every node is visited exactly once.

---

4. What is the space complexity?

Answer

O(h) where h is the height of the tree due to recursion or the explicit stack.

---

5. When should Preorder be used?

Answer

Preorder is useful for tree serialization, cloning, and creating prefix expressions.

---

6. Why is Inorder important for BSTs?

Answer

Because inorder traversal visits nodes in ascending sorted order for Binary Search Trees.

---

7. When is Postorder preferred?

Answer

Postorder is ideal for deleting trees, calculating subtree values, and evaluating expression trees.

---

8. Where is DFS used in production?

Answer

File systems, compiler AST traversal, dependency analysis, JSON/XML parsing, cloud infrastructure, AI decision trees, and version control systems.

---

9. What is the biggest mistake candidates make?

Answer

Forgetting the base case, causing infinite recursion or stack overflow.

---

10. How is DFS different from BFS?

Answer

DFS explores depth first using recursion or a stack, while BFS explores level by level using a queue.

---

Quick Revision

Topic	Summary
Pattern	Tree DFS
Traversal Types	Preorder, Inorder, Postorder
Data Structure	Stack / Recursion
Time Complexity	O(n)
Space Complexity	O(h)
Best For	Paths, Height, Subtrees
Interview Frequency	⭐⭐⭐⭐⭐

---

Key Takeaways

• Tree DFS is one of the most essential coding interview patterns for binary trees.
• It explores one branch completely before backtracking.
• Preorder, Inorder, and Postorder traversals each serve different purposes.
• Recursive DFS is concise and intuitive, while iterative DFS avoids recursion limits.
• Mastering DFS prepares you for advanced tree problems such as Lowest Common Ancestor, Diameter, Path Sum, Balanced Trees, and Binary Search Tree validation.

---