2385. Amount of Time for Binary Tree to Be Infected

Problem

You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.

Each minute, a node becomes infected if:

• The node is currently uninfected.

• The node is adjacent to an infected node.

Return the number of minutes needed for the entire tree to be infected.

  Example 1:

Input: root = [1,5,3,null,4,10,6,9,2], start = 3
Output: 4
Explanation: The following nodes are infected during:
- Minute 0: Node 3
- Minute 1: Nodes 1, 10 and 6
- Minute 2: Node 5
- Minute 3: Node 4
- Minute 4: Nodes 9 and 2
It takes 4 minutes for the whole tree to be infected so we return 4.

Example 2:

Input: root = [1], start = 1
Output: 0
Explanation: At minute 0, the only node in the tree is infected so we return 0.

  Constraints:

• The number of nodes in the tree is in the range [1, 105].

• 1 <= Node.val <= 105

• Each node has a unique value.

• A node with a value of start exists in the tree.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} start
 * @return {number}
 */
var amountOfTime = function(root, start) {
    const startNode = findStartNode(root, start, null);
    return findLongestPath(root, startNode, 0, {});
};

var findStartNode = function(node, start, parent) {
    if (!node) return null;
    const startNode = (node.val === start ? node : null)
        || findStartNode(node.left, start, node)
        || findStartNode(node.right, start, node);
    if (startNode) {
        node.parent = parent;
        return startNode;
    }
    return null;
};

var findLongestPath = function(root, node, depth, visited) {
    if (!node || visited[node.val]) return 0;
    visited[node.val] = true;
    if (!node.left && !node.right && !node.parent) return depth;
    return Math.max(
        node === root ? depth : 0,
        findLongestPath(root, node.left, depth + 1, visited),
        findLongestPath(root, node.right, depth + 1, visited),
        findLongestPath(root, node.parent, depth + 1, visited),
    );
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).