hardTreesPure DSA~30 min
Largest Value Gap Between a Node and an Ancestor
Across a tree of metric values, find the maximum absolute difference between any node and one of its ancestors.
Problem
Given the root of a binary tree, return the maximum value v for which there exist nodes a (an ancestor) and b (a descendant) with v = |a.val - b.val|.
Input
A binary tree root with integer node values.
Output
An integer: the maximum ancestor-descendant absolute difference.
Constraints
- 2 <= number of nodes <= 5000
- 0 <= node value <= 10^5
- The tree has at least one ancestor-descendant pair.
Examples
Example 1
Input
root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output
7
|8 - 1| = 7 is the largest gap along a root-to-leaf chain.
Example 2
Input
root = [1,null,2,null,0,3]
Output
3
|3 - 0| and |3 - 0| paths give a maximum gap of 3.