medium Find maximum depth of subtree

Problem Statement

Given the root node of a binary tree and an integer val, find the maximum depth of the subtree that starts from the node with the value equal to val. If the node with value val doesn't exist in the tree, return 0.

The depth of a node is defined as the number of edges on the longest path from the node to a leaf.

Examples

Example 1

• Input: root = [3, 5, 4, 2, null, 1, null, 6], val = 5

• Expected Output: 3
• Explanation: The subtree starting from the node with value 5 has nodes 5, 2, and 6. The maximum depth of this subtree is 3.

Example 2

• Input: root = [1, 2, 3, 4, null, null, 5, 6], val = 3

• Expected Output: 2
• Explanation: The subtree starting from the node with value 3 has nodes 3 and 5. The maximum depth of this subtree is 2.

Example 3

• Input: root = [7, 3, 9, 1, 6, null, 8, null, null, null, 2], val = 3

• Expected Output: 3
• Explanation: The subtree starting from the node with value 3 has nodes 3, 6, and 2. The maximum depth of this subtree is 3.

Solution

To solve this problem, we need to locate the node in the binary tree that has the value equal to val. Once we find this node, the task is to determine the depth of the subtree rooted at this node. Depth in this context means the number of edges on the longest path from the node to any of its leaf nodes.

We will utilize Depth-First Search (DFS) to explore all possible paths from the root node until we find the desired node. After locating the node, we continue the DFS to measure the depth of the subtree. This approach is efficient for this problem because DFS will allow us to traverse deep into the tree, ensuring we account for all possible depths before concluding.

Step-by-Step Algorithm

Part 1: Finding the Node with Value val

1. Start at the root node:

   • Begin the search from the root node of the tree.

2. Check if the tree is empty:

   • If the root is null, return 0 because the tree is empty.

3. Check if the current node's value matches val:

   • Compare the value of the current node (root.val) with the target value val.
   • If they match, proceed to the next part to calculate the depth of the subtree.

4. Search in the left subtree:

   • If the current node's value doesn't match val, recursively search in the left subtree by calling the method on root.left.

5. Search in the right subtree:

   • If the node is not found in the left subtree, recursively search in the right subtree by calling the method on root.right.

Part 2: Finding the Depth of the Subtree

1. Initialize the depth calculation at the found node:

   • Once the node with value val is found, start calculating the depth of the subtree rooted at this node.

2. Check if the current node is null:

   • If the current node is null, return 0 because a null node contributes no depth.

3. Calculate the depth of the left subtree:

   • Recursively call the depth calculation method on the left child of the current node.

4. Calculate the depth of the right subtree:

   • Recursively call the depth calculation method on the right child of the current node.

5. Determine the maximum depth:

   • For the current node, calculate the depth as 1 + max(leftDepth, rightDepth) where leftDepth and rightDepth are the depths of the left and right subtrees, respectively.

6. Return the calculated depth:

   • Return the depth calculated from the current node to its deepest leaf node, representing the depth of the subtree rooted at this node.

Algorithm Walkthrough

Input:

• Root: [3, 5, 4, 2, null, 1, null, 6]
• Val: 5

Step 1: Finding the Node with Value 5

1. Start at the root node with value 3:

   • The current node is 3. The value 3 does not match val = 5.
   • Proceed to search in the left subtree of node 3.

2. Move to the left child of node 3, which is 5:

   • The current node is now 5. The value 5 matches val = 5.
   • We have found the node where the subtree starts.

3. Proceed to calculate the depth of the subtree rooted at node 5:

   • Now that the node with value 5 is found, we move on to calculating the depth of the subtree rooted at this node.

Step 2: Calculating the Depth of the Subtree Rooted at Node 5

1. Calculate the depth of the left subtree of node 5:

   • Move to the left child of node 5, which is 2.
   • To find the depth of the subtree rooted at 2, proceed to its left child.

2. Move to the left child of node 2, which is 6:

   • The current node is 6. It has no left or right children, meaning it's a leaf node.
   • The depth of node 6 is 1 because there are no further children.

3. Calculate the depth of node 2:

   • Node 2 has a left depth of 1 (from node 6) and no right child.
   • The depth of node 2 is 1 + max(1, 0) = 2.

4. Calculate the depth of the right subtree of node 5:

   • The right child of node 5 is null, so the right depth is 0.

5. Determine the maximum depth of node 5:

   • Node 5 has a left depth of 2 (from node 2) and a right depth of 0.
   • The depth of node 5 is 1 + max(2, 0) = 3.

6. Return the depth of the subtree rooted at node 5:

   • The final output is 3, which represents the depth of the subtree starting from the node with value 5.

Code

// Define the TreeNode class
// class TreeNode {
//     int val; // Value of the node
//     TreeNode left; // Left child of the node
//     TreeNode right; // Right child of the node

//     // Constructor to initialize the node with a value
//     TreeNode(int val) {
//         this.val = val;
//         this.left = null;
//         this.right = null;
//     }
// }

// Define the Solution class
public class Solution {

  // Method to find the maximum depth of the subtree that starts with the node having value `val`
  public int maxDepthOfSubtree(TreeNode root, int val) {
    // If the tree is empty, return 0
    if (root == null) {
      return 0;
    }

    // If the current node's value matches `val`, calculate the maximum depth from here
    if (root.val == val) {
      return findMaxDepth(root);
    }

    // Recursively search in the left and right subtrees
    int leftDepth = maxDepthOfSubtree(root.left, val);
    int rightDepth = maxDepthOfSubtree(root.right, val);

    // Return the maximum depth found
    return Math.max(leftDepth, rightDepth);
  }

  // Helper method to calculate the depth of a given subtree
  private int findMaxDepth(TreeNode node) {
    // If the node is null, return 0 as the depth
    if (node == null) {
      return 0;
    }

    // Recursively find the depth of the left and right subtrees
    int leftDepth = findMaxDepth(node.left);
    int rightDepth = findMaxDepth(node.right);

    // The depth of the current node is 1 plus the maximum of the depths of its subtrees
    return 1 + Math.max(leftDepth, rightDepth);
  }

  // Main method to test the solution with example inputs
  public static void main(String[] args) {
    // Example 1:
    TreeNode root1 = new TreeNode(3);
    root1.left = new TreeNode(5);
    root1.right = new TreeNode(4);
    root1.left.left = new TreeNode(2);
    root1.right.left = new TreeNode(1);
    root1.left.left.left = new TreeNode(6);

    Solution solution1 = new Solution();
    System.out.println(solution1.maxDepthOfSubtree(root1, 5)); // Output: 3
  }
}

Complexity Analysis

• Time Complexity: The time complexity of the solution is , where N is the number of nodes in the binary tree. This is because we may need to traverse all nodes in the tree to find the node with value val and then calculate the depth of the subtree starting from that node.

• Space Complexity: The space complexity is , where H is the height of the binary tree. This is due to the recursive depth-first search (DFS) approach, which will require stack space proportional to the height of the tree.