Problem Statement

You are given the root of a binary tree with unique values and an integer start.

At the start time (minute 0), an infection starts from the node with the value start.

Each minute, a node becomes infected if:

• It is currently uninfected.
• It is adjacent to an infected node.

Return the number of minutes required for the entire tree to become infected.

Examples

Example 1:

• Input: root = [1, 2, 3, null, 4, 5, 6], start = 3
• Expected Output: 3
• Explanation: The tree structure is:

      1
     / \
    2   3
    \  / \
     4 5  6
  

  • Minute 0: Node 3 is infected.
  • Minute 1: Nodes 1, 5, and 6 become infected.
  • Minute 2: Node 2 becomes infected.
  • Minute 3: Node 4 becomes infected.
  • Total time: 3 minutes.

Example 2:

• Input: root = [1, 2, 3, 4, 5, null, null, 6, 7, null, null, null, null, 8, 9], start = 5
• Expected Output: 4
• Explanation: The tree structure is:

           1
         /   \
        2     3
       / \   
      4   5
     / \  
    6   7
   / \
  8   9
  

  • Minute 0: Node 5 is infected.
  • Minute 1: Nodes 2 become infected.
  • Minute 2: Nodes 1, and 4 become infected.
  • Minute 3: Nodes 3, 6 and 7 become infected.
  • Minute 4: Nodes 8 and 9 become infected.
  • Total time: 4 minutes.

Example 3:

• Input: root = [10, 1, 2, null, 3, 4, 5], start = 1
• Expected Output: 3
• Explanation: The tree structure is:

      10
     /  \
    1    2
     \  / \
      3 4  5
  

  • Minute 0: Node 1 is infected.
  • Minute 1: Nodes 10 and 3 become infected.
  • Minute 2: Nodes 2 become infected.
  • Minute 3: Nodes 4 and 5 become infected.
  • Total time: 3 minutes.

Constraints:

• The number of nodes in the tree is in the range [1, 10⁵].
• 1 <= Node.val <= 10⁵
• Each node has a unique value.
• A node with a value of start exists in the tree.

Try it yourself

Try solving this question here: