# 11.01.2024 [1026. Maximum Difference Between Node and Ancestor]

Max diff between node and ancestor in a binary tree.

11.01.2024

1026. Maximum Difference Between Node and Ancestor medium
blog post

youtube

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
  }