DIY: Maximum Difference Between Node and Ancestor

Problem statement

Given the root of a binary tree, find the maximum value, X, for which there exist two different nodes, A and B. X = |A.val - B.val|, and node A is an ancestor of node B.

Input

The following is an example input:

    3
   /  \
  5    1
  |   /  \
  2  15   7
 / \
7   4 

Output

The following is an example output:

12

Out of all the possible differences between the above tree’s two nodes, |3 - 15| = 12 gives the maximum value of 12.

Coding exercise

For this coding exercise, you need to implement the max_ancestor_diff(root) function, where root is the root node of the binary tree. The function will return the absolute maximum difference between any two ancestor-descendant nodes.