908. Time to Burn Binary Tree from a Node

Given the root of a binary tree and the value of a starting node, a fire starts at that node and each minute spreads to all adjacent nodes (parent and children). Return the number of minutes until the entire tree is burned. Node values are unique. The input gives a level-order tree array and the target value separated by ' | '.

Input: A level-order tree array and the target value, separated by ' | '.

Output: Integer — the minutes to burn the whole tree.

Examples

Input: [1,2,3,4,5,null,6,null,null,7,8] | 5
Output: 4
Explanation: Fire from node 5 takes 4 minutes.

Input: [1,2,3] | 1
Output: 1
Explanation: Spreads to both children in 1 minute.

Input: [1] | 1
Output: 0
Explanation: Already the whole tree.

Constraints

• 1<=nodes<=10^4
• node values unique
• target present

Asked by