LeetCode 1026 - Maximum Difference Between Node and Ancestor

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to find the largest absolute difference between the values of two nodes in a binary tree, under one important condition: one node must be an ancestor of the other.

In a binary tree, an ancestor of a node is any node that appears on the path from the root down to that node. A parent is an ancestor, a grandparent is also an ancestor, and so on.

For every node in the tree, we want to compare its value with the values of all descendants beneath it. Among all such ancestor-descendant pairs, we return the maximum absolute difference.

The input is the root of a binary tree. Each node contains:

An integer value
A left child pointer
A right child pointer

The output is a single integer representing the maximum possible value of:

$$|a.val - b.val|$$

where a is an ancestor of b.

The constraints are important:

The tree contains between 2 and 5000 nodes
Node values range from 0 to 100000

A tree with 5000 nodes is large enough that repeatedly traversing subtrees for every node could become too slow. This strongly suggests that we need an efficient traversal strategy that processes the tree in a single pass.

There are several important edge cases to consider:

A completely skewed tree, where every node only has one child. This effectively becomes a linked list and creates the maximum possible recursion depth.
A tree where all node values are identical. The answer should correctly become 0.
A tree where the maximum difference occurs between nodes that are far apart in depth, not just immediate parent-child pairs.
Trees where the minimum and maximum values appear on the same root-to-leaf path. This is where the largest difference usually emerges.

The problem guarantees at least two nodes, so there will always be at least one ancestor-descendant pair to evaluate.

Approaches

Brute Force Approach

A straightforward solution is to consider every node as a potential ancestor and compare it against every descendant in its subtree.

For each node:

Traverse all descendants beneath it.
Compute the absolute difference between the ancestor and each descendant.
Track the maximum difference found.

This approach is correct because it explicitly evaluates every valid ancestor-descendant pair.

However, it is inefficient. In the worst case, each node may traverse almost the entire remaining tree. For a tree with n nodes, this can lead to approximately:

$$O(n^2)$$

time complexity.

With up to 5000 nodes, quadratic behavior is unnecessarily expensive.

Key Insight for the Optimal Solution

The important observation is that for any node, the maximum difference involving that node depends only on:

The minimum value among its ancestors
The maximum value among its ancestors

Suppose we are currently visiting a node with value x.

If the ancestors along the path contain values ranging from minVal to maxVal, then the largest possible ancestor difference involving x must be:

$$\max(|x - minVal|,\ |x - maxVal|)$$

We do not need to remember every ancestor individually. We only need the smallest and largest values seen so far along the current root-to-node path.

This allows us to perform a single Depth-First Search traversal while carrying:

Current minimum ancestor value
Current maximum ancestor value

At each node:

Update the answer using the current min/max
Update min/max for children
Continue recursively

This reduces the solution to linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	For every node, traverse all descendants
Optimal DFS with Min/Max Tracking	O(n)	O(h)	Single traversal while tracking ancestor range

Here, h represents the height of the tree.

Algorithm Walkthrough

Optimal DFS with Min/Max Tracking

Start a Depth-First Search from the root node.

Since the root has no ancestors, initialize both the minimum and maximum ancestor values to the root's value. 2. At each node, calculate the difference against the current ancestor range.

The current path already contains all ancestors of this node. The maximum difference involving this node must come from either:

The smallest ancestor value
The largest ancestor value

Compute:

$$\max(|node.val - minVal|,\ |node.val - maxVal|)$$

Update the global answer if this value is larger. 3. Update the path minimum and maximum.

Since the current node becomes an ancestor for all descendants below it, update:

minVal = min(minVal, node.val)
maxVal = max(maxVal, node.val)

Recursively process the left subtree.

Pass the updated minimum and maximum values downward. 5. Recursively process the right subtree.

Again, pass the updated range. 6. Stop recursion when reaching a null node.

A null node means the path has ended, so simply return.

Why it works

The algorithm maintains an invariant during DFS:

minVal is the minimum value among all ancestors on the current path
maxVal is the maximum value among all ancestors on the current path

For every node, the largest possible ancestor difference must involve either the smallest or largest ancestor value. Since every root-to-node path is explored exactly once, every valid ancestor-descendant pair is implicitly considered.

Therefore, the algorithm correctly computes the maximum difference across the entire tree.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        self.answer = 0

        def dfs(node: Optional[TreeNode], current_min: int, current_max: int) -> None:
            if not node:
                return

            current_difference = max(
                abs(node.val - current_min),
                abs(node.val - current_max)
            )

            self.answer = max(self.answer, current_difference)

            updated_min = min(current_min, node.val)
            updated_max = max(current_max, node.val)

            dfs(node.left, updated_min, updated_max)
            dfs(node.right, updated_min, updated_max)

        dfs(root, root.val, root.val)

        return self.answer

The implementation uses recursive DFS to traverse the tree exactly once.

The variable self.answer stores the best result found globally across all paths.

The helper function dfs receives three pieces of information:

The current node
The minimum ancestor value on the current path
The maximum ancestor value on the current path

At each node, the code computes the largest difference between the node value and the current ancestor range.

Then the path range is updated so the current node becomes part of the ancestor set for deeper recursive calls.

The recursion naturally explores every root-to-node path, which guarantees all ancestor-descendant relationships are considered.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxAncestorDiff(root *TreeNode) int {
    answer := 0

    var dfs func(node *TreeNode, currentMin int, currentMax int)

    dfs = func(node *TreeNode, currentMin int, currentMax int) {
        if node == nil {
            return
        }

        diff1 := abs(node.Val - currentMin)
        diff2 := abs(node.Val - currentMax)

        currentDifference := max(diff1, diff2)

        if currentDifference > answer {
            answer = currentDifference
        }

        updatedMin := min(currentMin, node.Val)
        updatedMax := max(currentMax, node.Val)

        dfs(node.Left, updatedMin, updatedMax)
        dfs(node.Right, updatedMin, updatedMax)
    }

    dfs(root, root.Val, root.Val)

    return answer
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

The Go implementation follows the same logic as the Python solution.

Instead of using a class member variable, Go uses a local variable answer captured by the recursive closure.

Go does not provide built in min, max, or abs functions for integers, so helper functions are implemented manually.

Nil pointers are handled explicitly with:

if node == nil {
    return
}

Since node values are at most 100000, integer overflow is not a concern in Go's standard integer type.

Worked Examples

Example 1

Input:

root = [8,3,10,1,6,null,14,null,null,4,7,13]

Tree structure:

        8
      /   \
     3     10
    / \      \
   1   6      14
      / \     /
     4   7   13

DFS Traversal State

Current Node	Current Min	Current Max	Difference Computed	Global Answer
8	8	8	0	0
3	8	8	5	5
1	3	8	7	7
6	3	8	3	7
4	3	8	4	7
7	3	8	4	7
10	8	8	2	7
14	8	10	6	7
13	8	14	5	7

Final answer:

The maximum difference occurs between ancestor 8 and descendant 1.

Example 2

Input:

root = [1,null,2,null,0,3]

Tree structure:

DFS Traversal State

Current Node	Current Min	Current Max	Difference Computed	Global Answer
1	1	1	0	0
2	1	1	1	1
0	1	2	2	2
3	0	2	3	3

Final answer:

The maximum difference occurs between ancestor 0 and descendant 3.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack stores at most one root-to-leaf path

The DFS traversal processes each node a single time, performing only constant work per visit.

The space complexity depends on recursion depth. In a balanced tree, the height is approximately O(log n). In the worst case of a completely skewed tree, the height becomes O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxAncestorDiff(self, root):
        self.answer = 0

        def dfs(node, current_min, current_max):
            if not node:
                return

            current_difference = max(
                abs(node.val - current_min),
                abs(node.val - current_max)
            )

            self.answer = max(self.answer, current_difference)

            updated_min = min(current_min, node.val)
            updated_max = max(current_max, node.val)

            dfs(node.left, updated_min, updated_max)
            dfs(node.right, updated_min, updated_max)

        dfs(root, root.val, root.val)

        return self.answer

solution = Solution()

# Example 1
root1 = TreeNode(
    8,
    TreeNode(
        3,
        TreeNode(1),
        TreeNode(6, TreeNode(4), TreeNode(7))
    ),
    TreeNode(
        10,
        None,
        TreeNode(14, TreeNode(13))
    )
)
assert solution.maxAncestorDiff(root1) == 7  # standard example

# Example 2
root2 = TreeNode(
    1,
    None,
    TreeNode(
        2,
        None,
        TreeNode(
            0,
            TreeNode(3)
        )
    )
)
assert solution.maxAncestorDiff(root2) == 3  # skewed tree example

# All values identical
root3 = TreeNode(5, TreeNode(5), TreeNode(5))
assert solution.maxAncestorDiff(root3) == 0  # no difference anywhere

# Two node tree
root4 = TreeNode(1, TreeNode(100))
assert solution.maxAncestorDiff(root4) == 99  # simplest nontrivial case

# Deep left skewed tree
root5 = TreeNode(
    10,
    TreeNode(
        5,
        TreeNode(
            1,
            TreeNode(0)
        )
    )
)
assert solution.maxAncestorDiff(root5) == 10  # root versus deepest node

# Maximum difference not involving root
root6 = TreeNode(
    50,
    TreeNode(
        20,
        TreeNode(5),
        TreeNode(40)
    ),
    TreeNode(60)
)
assert solution.maxAncestorDiff(root6) == 45  # 50 -> 5 path

# Increasing chain
root7 = TreeNode(
    1,
    None,
    TreeNode(
        2,
        None,
        TreeNode(
            3,
            None,
            TreeNode(4)
        )
    )
)
assert solution.maxAncestorDiff(root7) == 3  # largest difference at ends

print("All test cases passed!")

Test Case Summary

Test	Why
Example 1 tree	Validates standard mixed structure
Example 2 skewed tree	Tests deep recursion and path tracking
All identical values	Ensures zero difference handled correctly
Two node tree	Smallest valid input
Deep left skewed tree	Worst case recursion depth
Maximum difference in subtree	Ensures all paths are considered
Increasing chain	Tests monotonic ancestor range updates

Edge Cases

Completely Skewed Tree

A tree where every node has only one child behaves like a linked list. This is important because recursion depth becomes equal to the number of nodes.

A buggy implementation might accidentally recompute values inefficiently or mishandle ancestor tracking across long paths.

This implementation handles skewed trees correctly because it maintains only two integers, the current minimum and maximum ancestor values, regardless of tree depth.

All Node Values Equal

If every node has the same value, every ancestor-descendant difference is zero.

Some implementations accidentally initialize the answer incorrectly or fail to handle this case when using subtraction logic.

This solution works correctly because every computed difference becomes:

abs(x - x) = 0

and the global maximum remains zero.

Maximum Difference Deep in the Tree

The largest difference may not involve the root node directly. It can occur entirely within a subtree.

For example:

The maximum difference here is 45, between 50 and 5.

A naive implementation that only compares parent-child pairs would fail.

This algorithm succeeds because it carries the entire ancestor range down the recursion path, not just the immediate parent value.