# 10.01.2024 [2385. Amount of Time for Binary Tree to Be Infected]
Max distance from node in a Binary Tree.
10.01.2024
2385. Amount of Time for Binary Tree to Be Infected medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/467
Problem TLDR
Max distance from node in a Binary Tree.
Intuition
Let’s build a graph, then do a Breadth-First Search from starting node.
Approach
We can store it in a parent[TreeNode]
map or just in two directional node to list<node>
graph.
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun amountOfTime(root: TreeNode?, start: Int): Int {
val fromTo = mutableMapOf<TreeNode, MutableList<TreeNode>>()
var queue = ArrayDeque<TreeNode>()
val visited = mutableSetOf<TreeNode>()
fun dfs(n: TreeNode): Unit = with (n) {
if (`val` == start) {
queue.add(n)
visited.add(n)
}
left?.let {
fromTo.getOrPut(n) { mutableListOf() } += it
fromTo.getOrPut(it) { mutableListOf() } += n
dfs(it)
}
right?.let {
fromTo.getOrPut(n) { mutableListOf() } += it
fromTo.getOrPut(it) { mutableListOf() } += n
dfs(it)
}
}
root?.let { dfs(it) }
var time = -1
while (queue.isNotEmpty()) {
repeat(queue.size) {
var x = queue.removeFirst()
fromTo[x]?.onEach {
if (visited.add(it)) queue.add(it)
}
}
time++
}
return time
}