Top-Down vs Bottom-Up Depth-First Search

In this post, we’ll explore two variations of depth-first search (DFS) algorithm to solve the binary tree based coding interview question.

Depth-first search (DFS) algorithm can be used in two different ways for solving specific problems: top-down and bottom-up.

Each approach has unique benefits depending on the type of problem. We’ll go over how each approach works, along with examples and code to help you understand the differences between them.

What is Depth-First Search (DFS)?

Depth-First Search is a traversal method for trees or graphs where we start at the root (or any arbitrary node) and explore each branch all the way down to the leaves.

This is done recursively, where each recursive call represents moving down a level in the tree.

Top-Down DFS Approach

In a top-down approach, we pass information from the root down to the leaves. For each recursive call, we typically carry some data from the root level of the tree downwards, updating it at each level as we go.

This approach is helpful in problems where we need to keep track of information such as the path from the root to the current node.

Example: Find the Maximum Depth of a Binary Tree

In this example, we’ll use the top-down approach to find the maximum depth of a binary tree by tracking the depth as we move from the root to each leaf node.

Code for Top-Down DFS

class Solution {    
    private int maxDepth = 0;

    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        
        dfs(root, 0);  // Start the DFS traversal with depth 0
        return maxDepth;
    }

    // TOP-DOWN DFS: Pass depth down from parent to children
    private void dfs(TreeNode node, int currentDepth) {
        currentDepth++;  // Increment depth as we go down each level

        // If the current depth is greater than the maxDepth, update maxDepth
        maxDepth = Math.max(maxDepth, currentDepth);

        // Traverse the left and right children if they exist
        if (node.left != null) {
            dfs(node.left, currentDepth);
        }
        if (node.right != null) {
            dfs(node.right, currentDepth);
        }
    }
}

Explanation of Top-Down DFS

1. Starting at the Root: We begin by calling dfs(root, 0), with a depth of 0.
2. Incrementing Depth: At each recursive call, we increase the depth by 1 as we move down each level.
3. Updating maxDepth: At each node, we compare currentDepth with maxDepth. If currentDepth is greater, we update maxDepth.
4. Base Case: If a node has no children (i.e., it’s a leaf), the function returns without further recursion, as that node’s depth is already counted when entering the dfs call.

Illustration of Top-Down DFS

Consider this binary tree:

       1
      / \
     2   3
    / \
   4   5

Here’s how the traversal proceeds:

1. We start at the root node (1) with currentDepth = 1.
2. Moving to node 2, the depth becomes 2.
3. Going down to node 4, currentDepth becomes 3. Since node 4 is a leaf, we backtrack and explore node 5, also reaching a depth of 3.
4. The maximum depth of the tree is ultimately found to be 3 after exploring all paths.

Bottom-Up DFS Approach

In a bottom-up approach, we solve the problem by gathering information from the leaves up to the root. Instead of passing data down, we calculate values at each level based on the values from lower levels.

This approach is useful when we need to make decisions based on information collected from subtrees.

Example: Find the Maximum Depth of a Binary Tree

We’ll solve the same problem using a bottom-up approach.

Code for Bottom-Up DFS

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return dfs(root);
    }

    // BOTTOM-UP DFS: No information is passed down; we return depth from children
    private int dfs(TreeNode node) {
        // Base case: if node is a leaf, depth is 1
        if (node.left == null && node.right == null) {
            return 1;
        }

        // Calculate the maximum depth of the left subtree
        int leftDepth = 0;
        if (node.left != null) {
            leftDepth = 1 + dfs(node.left);
        }

        // Calculate the maximum depth of the right subtree
        int rightDepth = 0;
        if (node.right != null) {
            rightDepth = 1 + dfs(node.right);
        }

        // Return the larger depth between the two subtrees
        return Math.max(leftDepth, rightDepth);
    }
}

Explanation of Bottom-Up DFS

1. Starting at the Leaves: We start from the root but only start returning values once we reach the leaves.
2. Calculating Depths from Subtrees: For each node, we calculate the maximum depth of its left and right subtrees.
3. Combining Results Upwards: We return the maximum depth from the left and right subtrees, adding 1 to account for the current node’s depth.
4. Final Result: When we reach back to the root, we compute the maximum depth of the entire tree based on the depth of left subtree and right subtree.

Illustration of Bottom-Up DFS

For the same binary tree:

       1
      / \
     2   3
    / \
   4   5

Here’s how the traversal proceeds:

1. Starting from the root, we recursively move down each path.
2. At the leaf nodes (4 and 5), we return a depth of 1.
3. For node 2, the maximum depth between its left and right children is 2.
4. The depth for node 3 is 1 since it has no children.
5. Finally, at the root (1), the maximum depth between its left and right children is 3, which is the maximum depth of the tree.

Key Differences Between Top-Down and Bottom-Up DFS

Summary

• Top-Down DFS is suitable for problems where you need to track cumulative information (e.g., paths or distances from the root).
• Bottom-Up DFS is useful when you need to gather results from subtrees and combine them at each level.

Each approach has its strengths, and understanding when to use each can greatly improve your problem-solving skills.

If you’re gearing up for coding interviews, Handbook for Coding Interviews book is the perfect prep guide. This book is packed with all the coding patterns and complete solutions to the most frequently asked coding interview questions.

If you found this post useful, please follow me on Medium. More to come.