Maximum Difference Between Node and Ancestor

Medium
1939.

Maximum Difference Between Node and Ancestor

Maximum Difference Between Node and Ancestor is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.

Given the root of a binary tree, find the largest value |a.val - b.val| over all pairs of different nodes a and b where a is an ancestor of b.

Node a is an ancestor of b when b is a child of a, or a child of some node that is itself a descendant of a — that is, a lies on the path from the root down to b.

Example 1

Input
root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output
7
Explanation
Among all ancestor-descendant pairs the widest gap is between 8 and its descendant 1: |8 - 1| = 7.

Example 2

Input
root = [1,null,2,null,0,3]
Output
3
Explanation
The chain is 1 → 2 → 0 → 3; the pair 0 (ancestor) and 3 (descendant) gives |0 - 3| = 3.

Example 3

Input
root = [6,6,6]
Output
0
Explanation
Every value is the same, so every difference is 0.

Constraints

  • 2 <= number of nodes <= 5000
  • 0 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxAncestorDiff = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Difference Between Node and Ancestor — Solution

Maximum Difference Between Node and Ancestor solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Difference Between Node and Ancestor is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the root of a binary tree, find the largest value |a.val - b.val| over all pairs of different nodes a and b where a is an ancestor of b.

Node a is an ancestor of b when b is a child of a, or a child of some node that is itself a descendant of a — that is, a lies on the path from the root down to b.

Example 1

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: Among all ancestor-descendant pairs the widest gap is between 8 and its descendant 1: |8 - 1| = 7.

Example 2

Input: root = [1,null,2,null,0,3]
Output: 3
Explanation: The chain is 1 → 2 → 0 → 3; the pair 0 (ancestor) and 3 (descendant) gives |0 - 3| = 3.

Example 3

Input: root = [6,6,6]
Output: 0
Explanation: Every value is the same, so every difference is 0.

Constraints

  • 2 <= number of nodes <= 5000
  • 0 <= Node.val <= 10^5

Hints for Maximum Difference Between Node and Ancestor

  1. Hint 1

    For a fixed node b, the best ancestor to pair it with is either the smallest or the largest value on the path from the root to b.

  2. Hint 2

    So it is enough to carry the minimum and the maximum seen so far down every root-to-node path.

  3. Hint 3

    When a path ends (you step past a leaf), the widest gap on that path is simply max - min; the answer is the largest such gap over all paths.

How to solve Maximum Difference Between Node and Ancestor

Any ancestor-descendant pair lies on one root-to-leaf path, and on a path the widest gap is between its smallest and largest values. Carry the running minimum and maximum down each path and take max - min at its end.

Approach

  1. Start a depth-first walk at the root with lo = hi = root.val.
  2. At each node, update lo = min(lo, node.val) and hi = max(hi, node.val).
  3. When the walk reaches a null child, return hi - lo for the path that just ended.
  4. Each node returns the larger of its two children's results; the root's result is the answer.

Why it works

Both nodes of a pair lie on the path from the root to the deeper one, so every pair is covered by some root-to-leaf path. Conversely the minimum and maximum of a path are themselves an ancestor-descendant pair (or the same node, giving 0), so max - min is achievable and no pair on the path does better.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion, h the height

Pitfalls

  • Comparing each node only with its parent misses gaps that span several levels.
  • Carrying only the minimum (or only the maximum) misses pairs where the descendant is smaller than its ancestor.

Reference solution

Python

from typing import Optional

def maxAncestorDiff(root: Optional[TreeNode]) -> int:
    def walk(node, lo, hi):
        if node is None:
            return hi - lo
        lo = min(lo, node.val)
        hi = max(hi, node.val)
        return max(walk(node.left, lo, hi), walk(node.right, lo, hi))

    return walk(root, root.val, root.val)

Java

public static int maxAncestorDiff(TreeNode root) {
    return diffWalk(root, root.val, root.val);
}

static int diffWalk(TreeNode node, int lo, int hi) {
    if (node == null) return hi - lo;
    lo = Math.min(lo, node.val);
    hi = Math.max(hi, node.val);
    return Math.max(diffWalk(node.left, lo, hi), diffWalk(node.right, lo, hi));
}

C++

int diffWalk(TreeNode* node, int lo, int hi);

int maxAncestorDiff(TreeNode* root) {
    return diffWalk(root, root->val, root->val);
}

int diffWalk(TreeNode* node, int lo, int hi) {
    if (!node) return hi - lo;
    lo = min(lo, node->val);
    hi = max(hi, node->val);
    return max(diffWalk(node->left, lo, hi), diffWalk(node->right, lo, hi));
}

JavaScript

var maxAncestorDiff = function(root) {
    return diffWalk(root, root.val, root.val);
};

var diffWalk = function(node, lo, hi) {
    if (node === null) return hi - lo;
    lo = Math.min(lo, node.val);
    hi = Math.max(hi, node.val);
    return Math.max(diffWalk(node.left, lo, hi), diffWalk(node.right, lo, hi));
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals