DIY: Maximum Difference Between Node and Ancestor

Solve the interview question "Maximum Difference Between Node and Ancestor" in this lesson.

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 maxAncestorDiff(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.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.