Maximum Difference Between Node and Ancestor
Last Updated: November 14, 2025
Problem Description
Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.
A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.
Example 1:
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
Example 2:
Output: 3
Constraints:
- The number of nodes in the tree is in the range
[2, 5000]. - 0 <= Node.val <= 105
Solve it on LeetCode
Approaches
1. Recursive DFS Approach
Intuition:
The problem is asking us to find the maximum difference between a node and its ancestor. This suggests a tree traversal technique where we either calculate the max difference for each node recursively or store the maximum/minimum value as we traverse.
Let's start by using a Depth-First Search (DFS) approach where for each node, we compute the maximum difference using its direct ancestors (i.e., the nodes along its path to the root).
Steps:
- Perform a DFS traversal starting from the root node.
- For each node, calculate the maximum difference between the node's value and the maximum and minimum values observed so far in the DFS path.
- Store and update the global maximum difference if it's greater than the previously recorded difference.
- Traverse both left and right children, updating the path's maximum and minimum values accordingly.
Code:
- Time Complexity: O(N), where N is the number of nodes in the tree, as we visit each node once.
- Space Complexity: O(H), where H is the height of the tree, representing the maximum depth of the recursive call stack.