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:
[2, 5000].0 <= Node.val <= 105Problem Overview: You are given the root of a binary tree. For any node, an ancestor is any node on the path from the root to that node. The task is to compute the maximum value of |ancestor.val - node.val| across all such pairs in the tree.
Approach 1: Depth First Search with Min/Max Tracking (Time: O(n), Space: O(h))
This is the optimal strategy and the one most interviewers expect. Traverse the tree using DFS while carrying two values along the path: the minimum value and maximum value seen from the root to the current node. At each step, update the answer using max(abs(node.val - minVal), abs(node.val - maxVal)). Then update the running minVal and maxVal before exploring children. Every node is processed once, so the time complexity is O(n), where n is the number of nodes. The recursion stack uses O(h) space where h is the tree height. This approach works because the largest difference for a node must come from either the smallest or largest ancestor value along its path.
This technique is a classic pattern when working with tree traversal problems. Instead of storing the entire ancestor list, you keep only the extremes needed to compute the maximum difference.
Approach 2: Breadth First Search (Iterative) (Time: O(n), Space: O(n))
You can also solve the problem using an iterative BFS with a queue. Each queue entry stores a tuple: (node, minVal, maxVal). Start with the root where both values equal root.val. For every node popped from the queue, compute the difference with the tracked min and max, update the global answer, then push children with updated ranges. The logic mirrors the DFS solution but replaces recursion with an explicit queue.
This approach also processes every node exactly once, giving O(n) time complexity. However, the queue can grow to the width of the tree, so the space complexity becomes O(n) in the worst case. BFS is useful if you prefer iterative solutions or want to avoid recursion depth issues.
Both methods rely on the same insight: the maximum difference at a node depends only on the minimum and maximum values seen among its ancestors. The traversal simply propagates those values while exploring the tree using either Depth-First Search or level-order traversal on a Binary Tree.
Recommended for interviews: Use the DFS min/max tracking approach. It is concise, runs in O(n) time with O(h) space, and clearly demonstrates understanding of recursive tree traversal. Mentioning the BFS alternative shows deeper understanding, but the DFS version is typically the cleanest implementation during interviews.
This approach leverages Depth First Search (DFS) to explore the binary tree. The key idea is to maintain the minimum and maximum values observed along the path from the root to the current node. By comparing the current node's value with these min/max values, we can compute potential maximum differences. As we backtrack, we use these values to determine the maximum difference possible for subtree paths.
The function maxAncestorDiffHelper is a recursive helper function that traverses the binary tree using DFS. It keeps track of the current path's minimum and maximum values as parameters. At each node, it updates these values and calculates differences, eventually returning the maximum found.
Time Complexity: O(n), where n is the number of nodes in the binary tree, because we visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursive stack usage.
This approach utilizes an iterative Breadth First Search (BFS) paradigm using a queue to traverse the tree. Queue elements consist of a node and associated min/max values for the path leading to this node. As nodes are processed, the difference between node values and min/max path values are calculated to find the maximum difference.
In this solution, a queue is used for BFS traversal, storing node and path min/max values. For each node, we compute current possible differences and keep track of the maximum difference encountered. The solution efficiently processes tree traversal iteratively.
Python
Time Complexity: O(n), as each node is visited once.
Space Complexity: O(n), for the queue storing the nodes in the worst case (when the tree is bushy).
For each node, to find the maximum difference with its ancestor nodes, we only need to find the difference between the maximum and minimum values of the ancestor nodes. The maximum difference among all nodes and their ancestor nodes is the answer.
Therefore, we design a function dfs(root, mi, mx), where the current node being searched is root, the maximum value of its ancestor nodes is mx, and the minimum value is mi. The function updates the maximum difference ans.
The logic of the function dfs(root, mi, mx) is as follows:
root is null, return directly.ans = max(ans, |mi - root.val|, |mx - root.val|).mi = min(mi, root.val), mx = max(mx, root.val), and recursively search the left and right subtrees.In the main function, we call dfs(root, root.val, root.val), and finally return ans.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
JavaScript
C#
| Approach | Complexity |
|---|---|
| Depth First Search with Min/Max Tracking | Time Complexity: O(n), where n is the number of nodes in the binary tree, because we visit each node exactly once. |
| Breadth First Search (Iterative) | Time Complexity: O(n), as each node is visited once. |
| DFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Min/Max Tracking | O(n) | O(h) | Best general solution. Clean recursive logic and optimal memory for balanced trees. |
| Iterative BFS with Range Tracking | O(n) | O(n) | Useful when avoiding recursion or when implementing level-order traversal iteratively. |
Maximum Difference Between Node and Ancestor | Brute Force | Optimal | Google | Leetcode 1026 • codestorywithMIK • 13,714 views views
Watch 9 more video solutions →Practice Maximum Difference Between Node and Ancestor with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor