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.