Maximum Difference Between Node and Ancestor
MedPrompt
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:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.Example 2:
Input: root = [1,null,2,null,0,3]
Output: 3
Constraints:
- The number of nodes in the tree is in the range
[2, 5000]. 0 <= Node.val <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward brute-force method. It iterates through each node of the tree, considering it as an ancestor a. For each such ancestor, it then performs another traversal through all of its descendants b. For every ancestor-descendant pair (a, b), it calculates the absolute difference of their values, |a.val - b.val|, and updates a global maximum value. This ensures that every possible pair is checked.
Algorithm
- Initialize a global variable
maxDifferenceto 0. - Create a main traversal function, e.g.,
traverseForAllAncestors(node), which will iterate through every node in the tree using DFS. - For each
nodevisited by this main traversal, consider it as a potentialancestor. - From this
ancestornode, start a second, inner DFS traversal, e.g.,findMaxDiffWithDescendants(ancestor, descendant). - In the inner traversal, for every
descendantnode in the subtree of theancestor, calculate the absolute difference:diff = |ancestor.val - descendant.val|. - Update the global
maxDifferencewith thisdiffif it's larger than the current maximum. - After the outer traversal completes,
maxDifferencewill hold the result.
Walkthrough
The core idea is to systematically check every valid ancestor-descendant pair. We can implement this using two nested traversals. The outer traversal selects a node to be the ancestor. The inner traversal explores the entire subtree of that ancestor node.
For example, if we have a DFS function outer_dfs(node) that traverses the whole tree. When outer_dfs is at a node u, we call another function inner_dfs(u, v) which starts with v=u and explores all nodes in the subtree of u. Inside inner_dfs, we calculate |u.val - v.val| and update our answer. This process guarantees that we compare every node with all of its descendants.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { int maxDifference = 0; public int maxAncestorDiff(TreeNode root) { if (root == null) { return 0; } // Outer traversal to select each node as a potential ancestor traverseForAllAncestors(root); return maxDifference; } private void traverseForAllAncestors(TreeNode ancestorNode) { if (ancestorNode == null) { return; } // For the current ancestor, find the max difference with all its descendants findMaxDiffWithDescendants(ancestorNode, ancestorNode); // Continue to other nodes traverseForAllAncestors(ancestorNode.left); traverseForAllAncestors(ancestorNode.right); } private void findMaxDiffWithDescendants(TreeNode ancestor, TreeNode descendant) { if (descendant == null) { return; } // Calculate and update the maximum difference maxDifference = Math.max(maxDifference, Math.abs(ancestor.val - descendant.val)); // Recurse for descendants findMaxDiffWithDescendants(ancestor, descendant.left); findMaxDiffWithDescendants(ancestor, descendant.right); }}Complexity
Time
O(N^2) in the worst case (for a skewed tree) and O(N log N) in the best case (for a balanced tree). For each of the N nodes, we traverse its subtree. The sum of all subtree sizes is O(N^2) in the worst case.
Space
O(N) in the worst case. The space is dominated by the recursion stack depth. For a skewed tree, the depth of both the outer and inner traversals can be up to N.
Trade-offs
Pros
Conceptually simple and easy to follow.
Guaranteed to be correct as it checks all possibilities.
Cons
Highly inefficient due to its time complexity, which is quadratic in the worst case.
Performs many redundant calculations. The difference between a node and its grandparent is calculated when the grandparent is the ancestor, and again when the parent is the ancestor (as part of its descendant traversal).
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private int ans ; public int MaxAncestorDiff ( TreeNode root ) { dfs ( root , root . val , root . val ); return ans ; } private void dfs ( TreeNode root , int mi , int mx ) { if ( root == null ) { return ; } int x = Math . Max ( Math . Abs ( mi - root . val ), Math . Abs ( mx - root . val )); ans = Math . Max ( ans , x ); mi = Math . Min ( mi , root . val ); mx = Math . Max ( mx , root . val ); dfs ( root . left , mi , mx ); dfs ( root . right , mi , mx ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.