Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Introduction to Tree Depth First Search Pattern
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

The Tree Depth-First Search (DFS) traversal is a key technique in binary tree operations. It focuses on exploring one branch of the tree as far as possible before backtracking. This approach is useful for problems requiring tree traversal or handling hierarchical data.

The main types of DFS traversals include:

  • Pre-order Traversal: Visit the root node first, then the left subtree, and finally the right subtree.
  • In-order Traversal: Visit the left subtree first, then the root node, and finally the right subtree.
  • Post-order Traversal: Visit the left and right subtrees first, and then the root node.

These techniques we have already discussed in the introduction chapter.

To solve DFS-based problems, the approach generally involves:

  • Recursive approach: Simple and follows the natural structure of a tree.
  • Iterative approach: Uses a stack to mimic recursion and helps in memory optimization.

DFS is ideal for scenarios where exploring entire paths or working with node relationships is essential.

Let's understand the Tree DFS (Depth-First Search) traversal via the below problem.

Problem Statement

Given the root of a binary tree, explore all possible root-to-leaf paths, compute the sum of values along each path, and return the minimum sum.

A leaf node is a node with no children.

Examples

Example 1:

  • Input: root = [10, 5, 15, null, null, 7, 20]
Image
  • Expected Output: 15
  • Justification: The path with the minimum sum is 10 -> 5. The sum is 10 + 5 = 15.

Example 2:

  • Input: root = [-1, 2, 3, 4, 5, 1]
Image
  • Expected Output: 3
  • Justification: The path with the minimum sum is -1 -> 3 -> 1. The sum is -1 + 3 + 1 = 3.

Example 3:

  • Input: root = [8, 40, 12, null, null, 10, 18, 2]
Image
  • Expected Output: 32
  • Justification: The path with the minimum sum is 8 -> 12 -> 10 -> 2. The sum is 8 + 12 + 10 + 2 = 32.

Solution

The algorithm calculates the minimum root-to-leaf path sum in a binary tree using a recursive approach. Starting at the root, it recursively explores the left and right subtrees, computes the minimum sum for each subtree, and adds the current node's value to the smaller of the two sums.

The base case is when the node is null, in which case the function returns 0. The recursion proceeds until it reaches the leaf nodes, and the minimum of the left and right sums is computed as it go back to the parent node of the particular node in the tree.

Step-by-Step Algorithm

  1. Base Case for Null Nodes:

    • If the current node (root) is null, return Integer.MAX_VALUE. This ensures that we do not consider non-existent paths while calculating the minimum sum.

  2. Base Case for Leaf Nodes:

    • If the current node is a leaf node (i.e., both left and right children are null), return the current node’s value (root.val) as a minimum sum. A leaf node is the endpoint of a valid path.

  3. Recursive Case for Non-leaf Nodes:

    • Step 3.1: Recursively compute the minimum sum for the left subtree by calling the same function on root.left.
    • Step 3.2: Recursively compute the minimum sum for the right subtree by calling the same function on root.right.

  4. Minimum Sum Calculation:

    • After computing the minimum sums for both the left and right subtrees, take the smaller of the two values using min(leftSum, rightSum).

  5. Add Current Node's Value:

    • Add the current node's value to the minimum of the left and right subtree sums.

  6. Return the Result:

    • Return the computed minimum root-to-leaf sum for the current node.

Algorithm Walkthrough

Image

Step 1: Start at the root node (-1)

  • The current node value is -1.
  • We need to calculate the minimum root-to-leaf path sum for both its left subtree (2) and right subtree (3).

Step 2: Traverse the left subtree of node (-1) (node 2)

  • The current node is 2.
  • We now need to calculate the minimum sum for both the left subtree (4) and the right subtree (5) of node 2.

Step 3: Traverse the left child of node 2 (node 4)

  • The current node is 4.
  • 4 is a leaf node (both children are null), so we return its value, which is 4.

Step 4: Traverse the right child of node 2 (node 5)

  • The current node is 5.
  • 5 is a leaf node (both children are null), so we return its value, which is 5.

Step 5: Calculate the minimum sum for node 2

  • Now that we have the sums for both children of node 2:
    • Left subtree (node 4) sum: 4
    • Right subtree (node 5) sum: 5
  • The minimum sum from node 2 to a leaf is:
    2 + min(4, 5) = 2 + 4 = 6.

Step 6: Traverse the right subtree of node (-1) (node 3)

  • The current node is 3.
  • We now need to calculate the minimum sum for its left subtree (1) (node 3 has no right child).

Step 7: Traverse the left child of node 3 (node 1)

  • The current node is 1.
  • 1 is a leaf node (both children are null), so we return its value, which is 1.

Step 8: Calculate the minimum sum for node 3

  • Since node 3 only has a left child:
    • Left subtree (node 1) sum: 1
  • The minimum sum from node 3 to a leaf is:
    3 + 1 = 4.

Step 9: Calculate the minimum sum for the root node (-1)

  • Now that we have the sums for both subtrees of the root node -1:
    • Left subtree (node 2) sum: 6
    • Right subtree (node 3) sum: 4
  • The minimum sum from the root -1 to a leaf is:
    -1 + min(6, 4) = -1 + 4 = 3.

Final Result:

The minimum root-to-leaf path sum for the given tree is 3, following the path -1 -> 3 -> 1.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. This is because the algorithm visits every node exactly once, performing constant-time work at each node (i.e., calculating the minimum of the left and right subtrees).

Space Complexity

The space complexity is determined by the recursion stack.

In the worst case (for example, a completely unbalanced tree), the space complexity can be O(N), as the recursion stack may need to go as deep as the height of the tree, which could be N in the case of a skewed tree.

In the best case (a balanced binary tree), the space complexity is O(log N), where the maximum depth of recursion would be the height of the tree, which is log N for a balanced tree.

Now, let's start solving the problem on Tree DFS Pattern.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible