LeetCode Entry

2385. Amount of Time for Binary Tree to Be Infected

10.01.2024 medium 2024 kotlin

Max distance from node in a Binary Tree.

2385. Amount of Time for Binary Tree to Be Infected medium blog post substack youtube image.png

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
  }