Burning Tree

Given a binary tree and a node data called target. Find the minimum time required to burn the complete binary tree if the target is set on fire. It is known that in 1 second all nodes connected to a given node get burned. That is its left child, right child, and parent.
Note: The tree contains unique values.

Examples : 

Input:      
          1
        /   \
      2      3
    /  \      \
   4    5      6
       / \      \
      7   8      9
                   \
                   10
Target Node = 8
Output: 7
Explanation: If leaf with the value 8 is set on fire. 
After 1 sec: 5 is set on fire.
After 2 sec: 2, 7 are set to fire.
After 3 sec: 4, 1 are set to fire.
After 4 sec: 3 is set to fire.
After 5 sec: 6 is set to fire.
After 6 sec: 9 is set to fire.
After 7 sec: 10 is set to fire.
It takes 7s to burn the complete tree.

Input:      
          1
        /   \
      2      3
    /  \      \
   4    5      7
  /    / 
 8    10
Target Node = 10
Output: 5

Expected Time Complexity: O(number of nodes)
Expected Auxiliary Space: O(height of tree)

Constraints:
1 ≤ number of nodes ≤ 10⁵

1 ≤ values of nodes ≤ 10⁵

Approach 01:

#include <algorithm>

class Solution {
 public:
    // Helper function to calculate the maximum distance to target and update maxTime
    int findMinTimeToTarget(Node* node, int& target, int& maxTime) {
        if (node == nullptr)
            return 0;
        
        // Recursively find distances in the left and right subtrees
        int leftDistance = findMinTimeToTarget(node->left, target, maxTime);
        int rightDistance = findMinTimeToTarget(node->right, target, maxTime);
        
        // If current node is the target, update maxTime with the longest distance found
        if (node->data == target) {
            maxTime = std::max(maxTime, std::max(leftDistance, rightDistance));
            return -1;
        } else {
            // If both subtrees contain valid distances
            if (leftDistance >= 0 && rightDistance >= 0)
                return std::max(leftDistance, rightDistance) + 1;

            // Ensure leftDistance is the smaller distance
            if (leftDistance > rightDistance)
                std::swap(leftDistance, rightDistance);

            // Update maxTime with the difference between right and left distances
            maxTime = std::max(maxTime, rightDistance - leftDistance);
            return leftDistance - 1;
        }
    }

    // Function to find the minimum time required to reach the target node
    int minTime(Node* root, int target) {
        int maxTime = 0;
        findMinTimeToTarget(root, target, maxTime);
        return maxTime;
    }
};

class Solution:
    def findMinTimeToTarget(self, node, target, maxTime):
        if node is None:
            return 0
        
        # Recursively find distances in the left and right subtrees
        leftDistance = self.findMinTimeToTarget(node.left, target, maxTime)
        rightDistance = self.findMinTimeToTarget(node.right, target, maxTime)
        
        # If current node is the target, update maxTime with the longest distance found
        if node.data == target:
            maxTime[0] = max(maxTime[0], max(leftDistance, rightDistance))
            return -1
        else:
            # If both subtrees contain valid distances
            if leftDistance >= 0 and rightDistance >= 0:
                return max(leftDistance, rightDistance) + 1

            # Ensure leftDistance is the smaller distance
            if leftDistance > rightDistance:
                leftDistance, rightDistance = rightDistance, leftDistance

            # Update maxTime with the difference between right and left distances
            maxTime[0] = max(maxTime[0], rightDistance - leftDistance)
            return leftDistance - 1

    def minTime(self, root, target):
        maxTime = [0]
        self.findMinTimeToTarget(root, target, maxTime)
        return maxTime[0]

Time Complexity

• Recursive Function Calls:

  The function findMinTimeToTarget recursively visits every node in the binary tree exactly once. Hence, the time complexity is proportional to the number of nodes in the tree.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \), where \( n \) is the number of nodes in the binary tree.

Space Complexity

• Recursive Call Stack:

  The space complexity due to the recursive call stack is \( O(h) \), where \( h \) is the height of the binary tree. In the worst case (a skewed tree), this can be \( O(n) \), but for a balanced binary tree, it is \( O(\log n) \).

• Additional Space:

  Other than the recursion stack, the function uses a constant amount of space for variables such as maxTime, leftDistance, and rightDistance, which is \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(h) \), where \( h \) is the height of the binary tree, with \( O(n) \) being the worst case for a skewed tree and \( O(\log n) \) for a balanced tree.