Getting Started with Trees: Depth First Search(DFS)

Welcome back!

This is the fourth installment of my blog series on trees. In the first blog, I talked about the basic definition and structure of trees, as well as the concepts of depth and height. In the second blog, I discussed various traversal methods that can be used to visit nodes in a tree. In the third blog, I specifically focused on binary trees, and their use in binary search algorithms.

DFS working principle as a gif

In this post, we’ll be exploring one of the fundamental algorithms for traversing trees (and graphs but we will look into this later on). Specifically, we’ll be diving deep into DFS, discussing what is it, how it works, and how we can use it to solve various problems.

So sit tight, grab a cup of coffee, and let’s get started!

What is Depth First Search?

In the context of trees, depth-first search (DFS) is a method of traversing a tree. It starts from the root node and explores as far as possible along each branch.

DFS can be helpful in various tree-related problems, such as finding a tree's height or maximum depth, checking if a tree is balanced, and searching for a node with a particular value. Also, it can be used in simulations of games (and game-like situations in the real world).

We can use recursion (or a stack for the iterative approach) to keep track of all the nodes while traversing.

Recursive DFS Example

Assume we have the following binary tree:

        1
       / \
      2   3
     / \   \
    4   5   6

We can perform a recursive DFS starting from the root node, using the following:

function Node(val, left, right) {
  this.val = val;
  this.left = left || null;
  this.right = right || null;
}

let root = new Node(1,
           new Node(2,
           new Node(4),
           new Node(5)),
           new Node(3,
           null,
           new Node(6)));

function DFS(node) {
  if (node === null) {
    return;
  }
  console.log(`Visiting node ${node.val}`);
  DFS(node.left);
  DFS(node.right);
}

DFS(root);

/* The output:
              Visiting node 1
              Visiting node 2
              Visiting node 4
              Visiting node 5
              Visiting node 3
              Visiting node 6
*/

The DFS function uses recursion to visit all the nodes in the tree. The algorithm first checks if the current node is null. If not, it performs any desired operation on the node(in this case it is printing the visited node value), and then recursively calls DFS on each of its child nodes.

Iterative DFS Example

By using the same tree, we can perform iterative DFS as:

function DFS(startNode) {
  let stack = [startNode];
  while (stack.length > 0) {
    let node = stack.pop();
    console.log(`Visiting node ${node.val}`);
    if (node.right !== null) {
      stack.push(node.right);
    }
    if (node.left !== null) {
      stack.push(node.left);
    }
  }
}

DFS(root);

The function uses a stack to visit all the nodes in the tree. The algorithm first pushes the start node onto the stack. Then, while the stack is not empty, it pops a node off the stack, performs any desired operation on the node, and pushes its child nodes (if any) onto the stack in reverse order (right child first, then left child).

DFS Related Problems

112. Path Sum

The problem: Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

The approach: We first check if the root is null, which means we have an empty tree and return false. Then, we check if we have reached a leaf node with a matching path sum, in which case we return true. If not, we continue the search on the left and right subtrees recursively, subtracting the current node’s value from the target sum.

var hasPathSum = function(root, targetSum) {
    if (!root) return false; // base case: empty tree
     // base case: leaf node with matching sum
    if (!root.left && !root.right && root.val === targetSum) return true;
    
    // recursive case: search left and right subtrees
    return hasPathSum(root.left, targetSum - root.val) 
           || hasPathSum(root.right, targetSum - root.val); 
};

Overall, this algorithm has a time complexity of O(n), where n is the number of nodes in the binary tree since we visit each node once.

The space complexity is O(h), where h is the tree's height since the maximum depth of the recursion is the tree's height.

Multiple questions can use DFS for path sum calculations. The upper example seems relatively simpler than what may be asked during an interview. Let’s see a harder question with similar logic.

437. Path Sum III

The question: Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf but must go downwards.

The approach: We can implement a helper function that checks whether the current node has a path that meets the criteria, and then recursively calls itself on the left and right subtrees to count the number of paths that start from those nodes.

Let’s see how we can implement such a function:

function countPathsFromNode(node, targetSum) {
    if (!node) {
        return 0; // empty node has no paths
    }
    
    // count the paths that end at this node and have the target sum
    let paths = node.val === targetSum ? 1 : 0;
    
    // count the paths that go through this node and continue downwards
    let pathsFromLeft = countPathsFromNode(node.left, targetSum - node.val);
    let pathsFromRight = countPathsFromNode(node.right, targetSum - node.val);
    
    // the total number of paths starting from this node is the sum of the 
    //two types of paths
    return paths + pathsFromLeft + pathsFromRight;
}

1. If the node is null, it means there are no paths that start from this node, so the function returns 0.
2. If it is not null, the function checks whether the node's value is equal to the target sum. If it is, it means there is at least one path so the function adds 1 to the paths variable.
3. The function then recursively calls itself on the left and right subtrees of the current node, passing in the difference between the target sum and the current node's value as the new target sum.
4. The result of the recursive call on the left and right subtree is stored.
5. Finally, the function returns the sum of paths and paths from left and right trees. This represents the number of paths starting from the current node and having a sum equal to the target.

Now, we can use this helper function in our main function.

var pathSum = function(root, targetSum) {
    if (!root) {
        return 0; // empty tree has no paths
    }
    
    // count the paths starting from the root and going downwards
    let pathsFromRoot = countPathsFromNode(root, targetSum);
    
    // count the paths starting from the left and right subtrees
    let pathsFromLeft = pathSum(root.left, targetSum);
    let pathsFromRight = pathSum(root.right, targetSum);
    
    // the total number of paths is the sum of the paths from all
    // starting points
    return pathsFromRoot + pathsFromLeft + pathsFromRight;
};

• The function countPathsFromNode is used to count the number of paths that start from a given node and have a sum equal to the target sum.
• If the root node is null, then the main function returns 0 since an empty tree has no paths.
• Otherwise, pathSum calls countPathsFromNode on the root node to count the paths starting from the root and going downwards.
• pathSum then recursively calls itself on the left and right subtrees of the root node, storing the results in the pathsFromLeft and pathsFromRight variables, respectively.
• Finally, pathSum returns the sum of pathsFromRoot, pathsFromLeft, and pathsFromRight. This represents the total number of paths in the binary tree that have a sum equal to the target sum.

98. Validate Binary Search Tree

The question: Given the root of a binary tree, determine if it is a valid binary search tree (BST).

The approach: We will take two other parameters to compare minimum and maximum values.

Initially, they will be equal to the minus and plus infinity for minimum and maximum respectively.

If the root doesn’t exist, we will return true since an empty tree is still a BST.

If it does, we will check its value.

• If the value is smaller than the min value or bigger than the maximum value, then the tree is not a binary search tree.

We will do this process with both the left and right children of the root.

Minimum and maximum values will be updated in each step.

• If we look for the left side of the tree, our maximum should be set to the current root value.
• If we look for the right side of the tree, our minimum should be set to the current root value.

This will be repeated until there is no more node to go.

Here is the implementation:

var isValidBST = function(root, min = -Infinity, max = Infinity) {
    if (!root) return true;
    if (root.val <= min || root.val >= max) return false;
    return isValidBST(root.left, min, root.val) &&
           isValidBST(root.right, root.val, max);
};

222. Count Complete Tree Nodes

The question: Given the root of a complete binary tree, return the number of nodes in the tree.

The approach: We can use a recursive method to solve this problem.

If the root is empty, the length is zero.

Assuming we have a root, we will return the function with the values of left and right subtrees and add 1 to the sum to count the current node.

var countNodes = function(root) {
    if(!root) return 0

    return 1 + countNodes(root.left) + countNodes(root.right)
};

236. Lowest Common Ancestor of a Binary Tree

The question: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

The approach: The function takes three arguments — the root of the binary tree, the two nodes p and q.

1. If the root is null or either p or q is the root, then the root itself is the lowest common ancestor. Therefore, the function returns the root.
2. Recursively call the function on the left and right subtrees of the root. The result of these calls would be the lowest common ancestor of p and q in the left and right subtrees respectively.
3. If both the left and right subtrees return a non-null value, then it means that p and q are present in different subtrees, and the current root is the lowest common ancestor. Therefore, the function returns the root.
4. If either the left or right subtree returns a non-null value, then it means that both p and q are present in the same subtree, and the lowest common ancestor is the node that was returned. Therefore, the function returns the non-null value.

Here is how we can implement it:

var lowestCommonAncestor = function(root, p, q) {
    if (!root || root === p || root === q) {
        return root;
    }
    
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    
    if (left && right) {
        return root;
    } else {
        return left ? left : right;
    }
};

This is a recursive algorithm that operates in O(n) time complexity, where n is the number of nodes in the binary tree.

Conclusion

We covered the definition of DFS in trees, both in the recursive and iterative approaches. We also solved several LeetCode problems that involved DFS traversal, which gave us a better understanding of how to apply DFS to solve real-world problems.

While DFS is quite useful in graphs as well, we focused on trees in this blog. In graphs, DFS can be used to find connected components, detect cycles, and solve other graph-related problems.

Overall, DFS is a versatile algorithm that can be applied to a wide range of problems in computer science and beyond. Whether you are working with trees or graphs, mastering DFS will undoubtedly help you become a better problem solver.