Maximum Difference Between Node and Ancestor

Leetcode Problem 1026: Maximum Difference Between Node and Ancestor

Problem Summary

Given the root of a binary tree, return the maximum absolute difference |a.val - b.val| where a is an ancestor of b (a node a is an ancestor of b if b lies on the path from a to any leaf).

Constraints:

• The tree has between 2 and 5,000 nodes.
• Node values are integers in the range [0, 100,000].

Techniques

• Tree
• Depth-First Search
• Binary Tree

Solution

export class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null

    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

interface SubTreeMaxMin {
    max: number
    min: number
}

function findDiff(root: TreeNode | null, currentMaxMin: SubTreeMaxMin): number {
    if (!root) {
        return currentMaxMin.max - currentMaxMin.min
    }

    const newMaxMin = {
        min: Math.min(currentMaxMin.min, root.val),
        max: Math.max(currentMaxMin.max, root.val)
    }
    const leftDiff = findDiff(root.left, newMaxMin)
    const rightDiff = findDiff(root.right, newMaxMin)

    return Math.max(rightDiff, leftDiff)
}

function maxAncestorDiff(root: TreeNode | null): number {
    const defaultMinMax = { max: -Infinity, min: Infinity }
    return findDiff(root, defaultMinMax)
}