LeetCode Entry

1026. Maximum Difference Between Node and Ancestor

11.01.2024 medium 2024 kotlin

Max diff between node and ancestor in a binary tree.

1026. Maximum Difference Between Node and Ancestor medium blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/468

Problem TLDR

Max diff between node and ancestor in a binary tree.

Intuition

Let’s traverse the tree with Depth-First Search and keep track of the max and min values.

Approach

  • careful with corner case: min and max must be in the same ancestor-child hierarchy
  • we can use external variable, or put it in each result

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\)

Code


  fun maxAncestorDiff(root: TreeNode?): Int {
    var res = 0
    fun dfs(n: TreeNode?): List<Int> = n?.run {
      (dfs(left) + dfs(right) + listOf(`val`)).run {
        listOf(min(), max()).onEach { res = max(res, abs(`val` - it)) }
      }
    } ?: listOf()
    dfs(root)
    return res
  }