Maximum Difference Between Node and Ancestor

Med

#0980Time: 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.2 companies

Algorithms

Depth-First Search

Data structures

Tree Binary Tree

Companies

EPAM Systems josh technology

Prompt

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 <= 10⁵

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 maxDifference to 0.
Create a main traversal function, e.g., traverseForAllAncestors(node), which will iterate through every node in the tree using DFS.
For each node visited by this main traversal, consider it as a potential ancestor.
From this ancestor node, start a second, inner DFS traversal, e.g., findMaxDiffWithDescendants(ancestor, descendant).
In the inner traversal, for every descendant node in the subtree of the ancestor, calculate the absolute difference: diff = |ancestor.val - descendant.val|.
Update the global maxDifference with this diff if it's larger than the current maximum.
After the outer traversal completes, maxDifference will 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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int maxDifference = 0;18 19    public int maxAncestorDiff(TreeNode root) {20        if (root == null) {21            return 0;22        }23        // Outer traversal to select each node as a potential ancestor24        traverseForAllAncestors(root);25        return maxDifference;26    }27 28    private void traverseForAllAncestors(TreeNode ancestorNode) {29        if (ancestorNode == null) {30            return;31        }32        // For the current ancestor, find the max difference with all its descendants33        findMaxDiffWithDescendants(ancestorNode, ancestorNode);34        35        // Continue to other nodes36        traverseForAllAncestors(ancestorNode.left);37        traverseForAllAncestors(ancestorNode.right);38    }39 40    private void findMaxDiffWithDescendants(TreeNode ancestor, TreeNode descendant) {41        if (descendant == null) {42            return;43        }44        45        // Calculate and update the maximum difference46        maxDifference = Math.max(maxDifference, Math.abs(ancestor.val - descendant.val));47        48        // Recurse for descendants49        findMaxDiffWithDescendants(ancestor, descendant.left);50        findMaxDiffWithDescendants(ancestor, descendant.right);51    }52}

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).

A much more efficient solution involves a single pass through the tree. As we traverse from the root down to the leaves, we can keep track of the minimum and maximum values encountered on the path so far. For any node, the maximum difference with an ancestor must be the difference between the node's value and either the minimum or maximum value seen on the path from the root to that node. This avoids the need for a nested traversal.

Algorithm

The key insight is that for any node b, the maximum difference |a.val - b.val| where a is an ancestor will occur when a.val is either the minimum or the maximum value among all its ancestors.
We can perform a single top-down DFS traversal.
We define a recursive helper function dfs(node, currentMin, currentMax).
currentMin and currentMax track the minimum and maximum values on the path from the root to the current node.
At each node, we calculate the difference between node.val and both currentMin and currentMax, and update a global maximum difference.
We then update currentMin and currentMax with node.val to include the current node in the path for its children.
We recursively call the function for the left and right children with the updated min and max values.
The initial call is dfs(root, root.val, root.val).

Walkthrough

We can implement this with a single recursive Depth-First Search (DFS) function. This function, let's call it findMaxDiff(node, currentMin, currentMax), will traverse the tree while maintaining the minimum and maximum values seen on the ancestor path.

When visiting a node:

We have currentMin and currentMax from its ancestors.
The maximum difference involving this node and one of its ancestors is max(|node.val - currentMin|, |node.val - currentMax|). We update our global answer with this value.
Before recursing to the children, we update the path's min/max values to include the current node: newMin = min(currentMin, node.val) and newMax = max(currentMax, node.val).
We then call the function on the left and right children with these new min/max values.

The process starts at the root, where the initial currentMin and currentMax are both root.val.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int maxDifference = 0;18 19    public int maxAncestorDiff(TreeNode root) {20        if (root == null) {21            return 0;22        }23        findMaxDiff(root, root.val, root.val);24        return maxDifference;25    }26 27    private void findMaxDiff(TreeNode node, int currentMin, int currentMax) {28        if (node == null) {29            return;30        }31 32        int potentialMaxDiff = Math.max(Math.abs(node.val - currentMin), Math.abs(node.val - currentMax));33        maxDifference = Math.max(maxDifference, potentialMaxDiff);34 35        int newMin = Math.min(currentMin, node.val);36        int newMax = Math.max(currentMax, node.val);37 38        findMaxDiff(node.left, newMin, newMax);39        findMaxDiff(node.right, newMax, newMax);40    }41}

Complexity

Time

O(N), where N is the number of nodes in the tree. Each node is processed exactly once during the traversal.

Space

O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H = N, leading to O(N) space. For a balanced tree, H = log N, leading to O(log N) space.

Trade-offs

Pros

Optimal time complexity as it visits each node only once.
Space efficient, especially for balanced trees.
Elegant and concise implementation.

Cons

The recursive implementation uses stack space, which could lead to a StackOverflowError for extremely deep trees (though not an issue with the given constraints).

Solutions

Solution

1/** * 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 ); } }

1/** * 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 { 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 ); } }

1/** * Definition for a binary tree node. * 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 =2  function (root) {3    let ans = 0;4    const dfs = (root, mi, mx) => {5      if (!root) {6        return;7      }8      ans = Math.max(ans, Math.abs(mi - root.val), Math.abs(mx - root.val));9      mi = Math.min(mi, root.val);10      mx = Math.max(mx, root.val);11      dfs(root.left, mi, mx);12      dfs(root.right, mi, mx);13    };14    dfs(root, root.val, root.val);15    return ans;16  };

1# 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 class Solution : def maxAncestorDiff ( self , root : Optional [ TreeNode ]) -> int : def dfs ( root , mi , mx ): if root is None : return nonlocal ans ans = max ( ans , abs ( mi - root . val ), abs ( mx - root . val )) mi = min ( mi , root . val ) mx = max ( mx , root . val ) dfs ( root . left , mi , mx ) dfs ( root . right , mi , mx ) ans = 0 dfs ( root , root . val , root . val ) return ans

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxAncestorDiff ( TreeNode * root ) { int ans = 0 ; function < void ( TreeNode * , int , int ) > dfs = [ & ]( TreeNode * root , int mi , int mx ) { if ( ! root ) { return ; } ans = max ({ ans , abs ( mi - root -> val ), abs ( mx - root -> val )}); mi = min ( mi , root -> val ); mx = max ( mx , root -> val ); dfs ( root -> left , mi , mx ); dfs ( root -> right , mi , mx ); }; dfs ( root , root -> val , root -> val ); return ans ; } };

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.

← Previous

Previous problem

Next problem