Amount of Time for Binary Tree to Be Infected

class Solution {
private:
    int greatestDistance = 0;

public:
    int totalTime(TreeNode* root, int start) {
        calculateTime(root, start);
        return greatestDistance;
    }

    int calculateTime(TreeNode* node, int start) {
        if (node == nullptr) {
            return 0;
        }

        int leftHeight = calculateTime(node->left, start);
        int rightHeight = calculateTime(node->right, start);

        if (node->val == start) {
            greatestDistance = max(leftHeight, rightHeight);
            return -1;
        } else if (leftHeight >= 0 && rightHeight >= 0) {
            return max(leftHeight, rightHeight) + 1;
        } else {
            int combinedDistance = abs(leftHeight) + abs(rightHeight);
            greatestDistance = max(greatestDistance, combinedDistance);
            return min(leftHeight, rightHeight) - 1;
        }
    }
};

This C++ solution addresses the problem of finding the amount of time required for a binary tree to be infected starting from a given node. The key components of this approach include:

• A private member greatestDistance to store the maximum distance calculated from the start node during the infection process.
• A public function totalTime which initializes the calculation by calling a helper function calculateTime.
• The calculateTime function recursively determines the time from any node to the furthest leaf in the binary tree. Here's how it functions:
  • If the current node is nullptr, it returns 0 indicating no further nodes to process.
  • Recursively calculate the height for left and right subtrees.
  • If the current node is the start node, the function sets greatestDistance to the higher of left or right subtree distances.
  • If neither child has reached the start node (leftHeight and rightHeight are non-negative), it calculates the distance to the next node in the path and propagates this upwards.
  • If either child has reached the start node (reflected by a negative height), this node captures the cumulative reach of the infection by adding the absolute values of left and right heights and updates greatestDistance as needed.
  • Returns the minimum of leftHeight or rightHeight minus one, to indicate the node is moving away from the infection start.

Each time calculation revolves around determining the maximum path length to leaf nodes and ensuring the node distances are correctly managed when propogating back towards the root node after identifying the start node. This mechanism allows the program to accurately compute the total time taken for the infection to spread through the binary tree, as represented by the maximum value stored in greatestDistance.

/**
 * Definition for a binary tree node.
 * public class BinaryTreeNode {
 *     int value;
 *     BinaryTreeNode leftNode;
 *     BinaryTreeNode rightNode;
 *     BinaryTreeNode() {}
 *     BinaryTreeNode(int value) { this.value = value; }
 *     BinaryTreeNode(int value, BinaryTreeNode leftNode, BinaryTreeNode rightNode) {
 *         this.value = value;
 *         this.leftNode = leftNode;
 *         this.rightNode = rightNode;
 *     }
 * }
 */
class Solution {

    private int maximumTime = 0;

    public int timeRequired(BinaryTreeNode rootNode, int startValue) {
        explore(rootNode, startValue);
        return maximumTime;
    }

    public int explore(BinaryTreeNode node, int target) {
        int currentDepth = 0;
        if (node == null) {
            return currentDepth;
        }

        int depthLeft = explore(node.leftNode, target);
        int depthRight = explore(node.rightNode, target);

        if (node.value == target) {
            maximumTime = Math.max(depthLeft, depthRight);
            currentDepth = -1;
        } else if (depthLeft >= 0 && depthRight >= 0) {
            currentDepth = Math.max(depthLeft, depthRight) + 1;
        } else {
            int maxPath = Math.abs(depthLeft) + Math.abs(depthRight);
            maximumTime = Math.max(maximumTime, maxPath);
            currentDepth = Math.min(depthLeft, depthRight) - 1;
        }

        return currentDepth;
    }
}

The provided Java program calculates the amount of time required for a given binary tree to be infected from a specific node. The binary tree is represented by nodes, each defined by a class BinaryTreeNode with attributes for the node's value and pointers to left and right child nodes.

The main functionality is found in the Solution class which contains methods to determine the time required for infection to reach all nodes once it starts from a specified node (startValue). Here’s how the solution works:

• Create a recursive function explore which traverses the tree. It returns the depth of infection spread from the start node to every other node, directly or indirectly connected.
• explore checks the current node:
  • If the node is null, it ends the recursion returning zero, indicating no further depth below this node.
  • For non-null nodes, the function recursively calls itself for the left and right children to calculate their depths.
  • If the current node is the starting node (node value equals startValue), it sets maximumTime to the maximum of the depths from its left or right subtree and indicates by returning -1 that it is the infected node.
  • If the returned values from left and right are both non-negative, combine these depths and update maximumTime if necessary.
  • If the node cannot be used to propagate further infection due to either subtree not connecting back to the infected subtree, it determines the path through the longest branch by adding distances and updates maximumTime respectively.

This algorithm efficiently finds the maximum time needed to propagate the infection to all nodes by leveraging depth-first search principles and making a single pass over the structure of the tree. Thus, this solution ensures minimized calculations and achieves an optimal solution for the proposed problem.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.max_distance = 0

    def amountOfTime(self, root, start):
        self.traverse(root, start)
        return self.max_distance

    def traverse(self, root, start):
        if root is None:
            return 0

        left_depth = self.traverse(root.left, start)
        right_depth = self.traverse(root.right, start)

        if root.val == start:
            self.max_distance = max(left_depth, right_depth)
            return -1
        else:
            if left_depth >= 0 and right_depth >= 0:
                return max(left_depth, right_depth) + 1
            else:
                distance = abs(left_depth) + abs(right_depth)
                self.max_distance = max(self.max_distance, distance)
                return min(left_depth, right_depth) - 1

In the provided Python3 solution, you determine the time needed for an infection to spread throughout a binary tree from the given start node. The solution encompasses defining a binary tree node structure and implementing a method to calculate this duration based on tree traversal.

Key components and steps of the solution:

• TreeNode Class Definition:

  • Nodes of the binary tree, each containing an integer value, and pointers to the left and right child nodes.

• Solution Class Construction:

  • Initializes max_distance to track the furthest distance covered during the infection spread.

• amountOfTime Method:

  • Initiates the tree traversal from the root to calculate the infection spread time.

• traverse Helper Function:

  • Traverses the tree recursively and conducts depth-first search.
  • Calculates distances from the start node to all other nodes.
  • Determines and updates the maximum distance the infection has to travel to reach all nodes.

• Distance Calculation Logic:

  • If the current node is the starting node, updates the max_distance to the greater depth of its child nodes.
  • If neither child reached the start node, the function moves up by adding one to the maximum depth obtained from children.
  • If either child reached the start node previously, computes the about-to-be-infected paths and updates the max_distance.

• Result Compilation:

  • Returns the max_distance, which reflects the furthest time from the start node to an uninfected node, representing the total time for the infection to cover the entire tree.

The efficiency of this solution depends on the structure of the tree and the position of the start node within it. The recursive depth-first approach ensures that all nodes are visited, and the maximum infection time is accurately computed.