# Coding Patterns: Depth First Search (DFS)

In **Coding Patterns** series, we will try to *recognize* common patterns *underlying* behind each algorithm question, using real examples from Leetcode.

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List and Breadth First Search (BFS) patterns and today, we will introduce Depth First Search (DFS) pattern which is very useful to solve the problems involving traversal of a tree.

We will be using recursion (or we can also use a Stack for the iterative approach) to keep track of all the previous (parent) nodes while traversing. This also means that the space complexity of the algorithm will be **O(H)**, where **H** is the *maximum height* of the tree.

## Problem: Path Sum

**LeetCode 112 - Path Sum** [*easy*]

Given a binary tree and a sum, determine if the tree has a *root-to-leaf* path such that adding up all the values along the path equals the given sum.

**Note:** A leaf is a node with no children.

**Example:**

Given the below binary tree and sum = 22,

```
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
```

return `true`

, as there exist a *root-to-leaf* path `5 -> 4 -> 11 -> 2`

which sum is **22**.

### Depth First Search Solution

As we are trying to search for a **root-to-leaf** path, we can use the Depth First Search (DFS) technique to solve this problem.

To recursively traverse a binary tree in a DFS fashion, we can start from the `root`

and at every step, make two recursive calls one for the `root.left`

and one for the `root.right`

child by subtracting the value of the current node from the given number: `sum - root.val`

.

```
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if root is None:
return False
if root.val == sum and root.left is None and root.right is None:
return True
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
```

**Time Complexity**: **O(N)** where ** N** is the total number of nodes in the tree.

**Space Complexity**: **O(N)**, this space will be used to store the recursion stack. The worst case will happen when the given tree is a linked list (i.e. *every* node has only *one* child)

## How to identify?

This approach is quite useful when dealing with the problems involving traversal of a tree.

When the problem asks the traversal of a tree, you should think about Depth First Search (DFS) pattern and using it in combination with a recursive approach.