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
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.
Given the below binary tree and sum = 22,
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
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.