Maximum Difference Between Node and Ancestor

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a binary tree with at least two nodes, find the largest value of |a.val - b.val| over all pairs of distinct nodes a and b where a is an **ancestor** of b. A node is an ancestor of b if it lies on the path from the root to b (a parent, grandparent, and so on); a node is not its own ancestor. Return that maximum absolute difference. Comparing every node against all of its ancestors is O(n * h). Carrying the minimum and maximum value seen along the current path reduces this to O(n).

Examples

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
The ancestor 8 and descendant 1 give |8 - 1| = 7, the largest difference.
Input: root = [1,null,2,null,0,3]
Output: 3
Node 0 is an ancestor of node 3, giving |0 - 3| = 3.

Constraints

  • 2 <= number of nodes <= 5000
  • 0 <= Node.val <= 10^5
  • Values may repeat (a difference of 0 is possible)

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems