1026. Maximum Difference Between Node and Ancestor
Problem Description
Given a binary tree, where each node contains an integer, we are asked to find the largest absolute difference in value between two nodes where one node is an ancestor of the other. In other words, if we pick any node a
as an ancestor, and any node b
as a descendant of a
, what is the maximum absolute difference between a.val
and b.val
(|a.val - b.val|
) that we can find in the tree?
An important detail to note is that a node can be considered an ancestor of itself, leading to a minimum absolute difference of 0 in such a scenario. The problem is focusing on finding the maximum difference, hence we need to look for pairs of ancestor and descendant nodes where this difference is the largest.
Flowchart Walkthrough
Let's use the flowchart to analyze the appropriate algorithm for solving LeetCode problem 1026. Maximum Difference Between Node and Ancestor. Here’s a step-by-step determination using the given flowchart:
Is it a graph?
- Yes: The structure provided is a binary tree, which is a type of graph where each node has at most two children.
Is it a tree?
- Yes: Specifically, the problem is defined on a binary tree.
DFS
- Given the nature of the tree (it is indeed a tree), the next logical step is to use Depth-First Search (DFS).
Conclusion: The flowchart leads us directly to utilizing a Depth-First Search (DFS) for this tree-based problem, as DFS is well-suited for exploring all paths and finding the maximum difference between a node and its ancestors. This approach allows us to efficiently traverse the tree, maintaining current maximum and minimum values as we move from root to leaves, comparing and updating the required maximum difference.
Intuition
The intuition behind the solution is that we can find the maximum difference by thoroughly searching through the tree. We do this using a depth-first search (DFS) algorithm, which will allow us to explore each branch of the tree to its fullest extent before moving on to the next branch.
During the traversal, we keep track of the minimum (mi
) and maximum (mx
) values encountered along the path from the root to the current node. At each node, we calculate the absolute difference between root.val
and both the mi
and mx
values, updating the global maximum ans
if we find a larger difference.
The core idea is to track the range of values (minimum and maximum) on the path from the root to the current node because this range will allow us to compute the required maximum absolute difference at each step. By the time we complete our traversal, we will have examined all possible pairs of ancestor and descendant nodes and thus found the maximum difference.
To implement this, we use a recursive helper function dfs(root, mi, mx)
that performs a depth-first search on the binary tree. The mi
and mx
parameters keep track of the minimum and maximum values respectively, seen from the root to the current node. The function also updates a nonlocal variable ans
, which keeps track of the maximum difference found so far.
Finally, we initiate our DFS with the root node and its value as both the initial minimum and maximum, and after completing the traversal, we return the value stored in ans
, which will be the maximum ancestor-difference that we were tasked to find.
Learn more about Tree, Depth-First Search and Binary Tree patterns.
Solution Approach
The solution to this problem involves a recursive depth-first search (DFS) algorithm to traverse the binary tree. The critical aspect of the approach is to maintain two variables, mi
and mx
, to record the minimum and maximum values found along the path from the root node to the current node.
Here is a step-by-step breakdown of the implementation details:
- Define a recursive helper function
dfs(root, mi, mx)
that will be used for DFS traversal of the tree. - If the current
root
isNone
, which means we've reached a leaf node's child, we return, as there are no more nodes to process in this path. - The helper function is designed to continuously update a nonlocal variable
ans
, which holds the maximum absolute difference found. - At each node, we compare and update
ans
with the absolute difference of the current node's valueroot.val
with both the minimum (mi
) and maximum (mx
) values seen so far along the path from the root. - We perform this comparison using
max(ans, abs(mi - root.val), abs(mx - root.val))
. - After updating
ans
, we also updatemi
andmx
for the recursive calls on the children nodes, settingmi
tomin(mi, root.val)
andmx
tomax(mx, root.val)
. This ensures that as we go deeper into the tree, our range[mi, mx]
remains updated with the smallest and largest values seen along the path. - Recursive calls are then made to continue the DFS traversal on the left child
dfs(root.left, mi, mx)
and the right childdfs(root.right, mi, mx)
of the current node.
The main function initializes the variable ans
to 0 and then calls dfs(root, root.val, root.val)
. We start with both mi
and mx
as the root's value, since initially, the root is the only node in the path. The implementation leverages the default argument-passing mechanism in Python, where every child node receives the current path's minimum and maximum values to keep the comparison going.
After the completion of the DFS traversal, the ans
variable, which was kept up-to-date during the traversal, will contain the final result—the maximum difference. The function finally returns ans
.
The primary data structure used in this implementation is the binary tree itself. No additional data structures are needed because the recursion stack implicitly manages the traversal, and the updating of minimum and maximum values is done using integer variables. This efficient use of space and recursive traversal makes it a neat and effective solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small binary tree to illustrate the solution approach. Our binary tree is as follows:
1 8 2 / \ 3 3 10 4 / \ \ 5 1 6 14 6 / \ / 7 4 7 13
We want to find the maximum absolute difference between the values of any two nodes where one is an ancestor of the other.
We begin by calling the recursive function dfs
on the root node with value 8
. We start with mi = mx = 8
since the root is both the minimum and maximum of the path consisting of just itself.
-
The
dfs
function is first called withroot.val = 8
,mi = 8
,mx = 8
. We are at the root. -
Explore left child (
3
). Calldfs(3, min(8,3), max(8,3))
:- Now
mi = 3
,mx = 8
. - Update potential answer compare with previous
ans
:max(0, abs(3 - 8), abs(8 - 3))
ans = 5
- Now
-
Go down to the left child of
3
, node1
. Calldfs(1, min(3,1), max(8,1))
:- Here,
mi = 1
,mx = 8
. - Update answer:
max(5, abs(1 - 8), abs(8 - 1))
ans = 7
Node
1
is a leaf; the traversal will go back up. - Here,
-
The other child of
3
is6
. Calldfs(6, min(3,6), max(8,6))
:mi = 3
,mx = 8
.- Update answer:
max(7, abs(3 - 6), abs(8 - 6))
ans
remains7
.
-
Node
6
has a left child4
. Calldfs(4, min(3,4), max(8,4))
:mi = 3
,mx = 8
.- Update answer:
max(7, abs(3 - 4), abs(8 - 4))
ans
remains7
.
Since
4
is a leaf node, we go back up. -
Node
6
also has right child7
. Calldfs(7, min(3,7), max(8,7))
:mi = 3
,mx = 8
.- Update answer:
max(7, abs(3 - 7), abs(8 - 7))
ans
remains7
.
Node
7
is also a leaf; traverse back up to3
, then to8
. -
Now explore right child (
10
) of the root. Calldfs(10, min(8,10), max(8,10))
:mi = 8
,mx = 10
.- Update answer:
max(7, abs(8 - 10), abs(10 - 8))
ans
remains7
.
-
Node
10
has right child14
. Calldfs(14, min(8,14), max(10,14))
:mi = 8
,mx = 14
.- Update answer:
max(7, abs(8 - 14), abs(14 - 8))
ans
becomes14 - 8 = 6
but since our currentans = 7
, there is no update.
-
Node
14
has a left child13
. Calldfs(13, min(8,13), max(14,13))
:mi = 8
,mx = 14
.- Update answer:
max(7, abs(8 - 13), abs(14 - 13))
ans
remains7
because the differences5
and1
are smaller than the currentans
.
After the recursive depth-first search completes, we find that the maximum absolute difference is 7
, which comes from the difference between nodes 8
(ancestor) and 1
(descendant).
Solution Implementation
1class TreeNode:
2 # A class for a binary tree node
3 def __init__(self, val=0, left=None, right=None):
4 self.val = val # Node value
5 self.left = left # Left child
6 self.right = right # Right child
7
8class Solution:
9 def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
10 # Helper function to perform Depth-First Search (DFS)
11 def dfs(node, min_value, max_value):
12 # Base case: if the current node is None, return
13 if node is None:
14 return
15
16 # Calculate the maximum difference for the current node
17 nonlocal max_difference
18 current_diff = max(abs(min_value - node.val), abs(max_value - node.val))
19 max_difference = max(max_difference, current_diff)
20
21 # Update the minimum and maximum values with the value of the current node
22 new_min = min(min_value, node.val)
23 new_max = max(max_value, node.val)
24
25 # Recursively call dfs for the left and right subtrees
26 dfs(node.left, new_min, new_max)
27 dfs(node.right, new_min, new_max)
28
29 # Initialize max_difference which will hold the result
30 max_difference = 0
31
32 # Start DFS from root with its value as both initial min and max
33 dfs(root, root.val, root.val)
34
35 # Return the maximum difference found
36 return max_difference
37
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8
9 TreeNode() {}
10
11 TreeNode(int val) {
12 this.val = val;
13 }
14
15 TreeNode(int val, TreeNode left, TreeNode right) {
16 this.val = val;
17 this.left = left;
18 this.right = right;
19 }
20}
21
22class Solution {
23 private int maxDifference;
24
25 /**
26 * Calculates the maximum difference between values of any two connected nodes in the binary tree.
27 * @param root The root of the binary tree.
28 * @return The maximum difference calculated.
29 */
30 public int maxAncestorDiff(TreeNode root) {
31 if (root == null) {
32 return 0;
33 }
34 // Start DFS with the initial value of the root for both minimum and maximum.
35 depthFirstSearch(root, root.val, root.val);
36 return maxDifference;
37 }
38
39 /**
40 * A recursive DFS function that traverses the tree to find the maximum difference.
41 * @param node The current node being visited.
42 * @param minVal The minimum value seen so far in the path from root to the current node.
43 * @param maxVal The maximum value seen so far in the path from root to the current node.
44 */
45 private void depthFirstSearch(TreeNode node, int minVal, int maxVal) {
46 if (node == null) {
47 return;
48 }
49
50 // Calculate the potential differences between the current node value and the observed min and max values.
51 int currentMaxDifference = Math.max(Math.abs(minVal - node.val), Math.abs(maxVal - node.val));
52
53 // Update the maxDifference if the current one is greater.
54 maxDifference = Math.max(maxDifference, currentMaxDifference);
55
56 // Update the min and max values to carry them forward in the DFS.
57 minVal = Math.min(minVal, node.val);
58 maxVal = Math.max(maxVal, node.val);
59
60 // Recur for both the left and right subtrees.
61 depthFirstSearch(node.left, minVal, maxVal);
62 depthFirstSearch(node.right, minVal, maxVal);
63 }
64}
65
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15 /* Function to calculate max difference between any ancestor and node value. */
16 int maxAncestorDiff(TreeNode* root) {
17 int maxDifference = 0; // to store the maximum difference
18
19 // Lambda function for depth-first search starting from 'node'
20 // It carries the current minimum and maximum values as 'currentMin' and 'currentMax'
21 function<void(TreeNode*, int, int)> dfs = [&](TreeNode* node, int currentMin, int currentMax) {
22 if (node == nullptr) {
23 // If the node is null, return as there is nothing to process
24 return;
25 }
26 // Update maxDifference with the maximum of the current difference
27 // and the differences with the current node's value
28 maxDifference = max({
29 maxDifference,
30 abs(currentMin - node->val),
31 abs(currentMax - node->val)
32 });
33
34 // Update currentMin and currentMax with respective minimum and maximum values
35 currentMin = min(currentMin, node->val);
36 currentMax = max(currentMax, node->val);
37
38 // Continue depth-first search on left and right subtrees
39 dfs(node->left, currentMin, currentMax);
40 dfs(node->right, currentMin, currentMax);
41 };
42
43 // Initialize DFS with the value of the root for both min and max
44 dfs(root, root->val, root->val);
45
46 // Return the maximum difference found
47 return maxDifference;
48 }
49};
50
1// Global variable to track the maximum difference between an ancestor and a node value
2let maxDifference: number = 0;
3
4// Recursive function traverses the tree to find the maximum difference between an ancestor and a node value
5function dfs(node: TreeNode | null, minVal: number, maxVal: number): void {
6 if (!node) {
7 // If node is null, return because we've reached a leaf node's child.
8 return;
9 }
10
11 // Calculate the potential new max differences with the current node
12 const potentialMaxDiff = Math.max(Math.abs(node.val - minVal), Math.abs(node.val - maxVal));
13
14 // Update the global maxDifference if the new potential difference is greater
15 maxDifference = Math.max(maxDifference, potentialMaxDiff);
16
17 // Update the min and max values seen so far after considering the current node's value
18 const newMinVal = Math.min(minVal, node.val);
19 const newMaxVal = Math.max(maxVal, node.val);
20
21 // Continue the DFS traversal for left and right children
22 dfs(node.left, newMinVal, newMaxVal);
23 dfs(node.right, newMinVal, newMaxVal);
24}
25
26// Primary function to initiate the maxAncestorDiff calculation, given the root of a binary tree
27function maxAncestorDiff(root: TreeNode | null): number {
28 if (root === null) {
29 // If the tree is empty, the maximum difference is 0 by definition
30 return 0;
31 }
32
33 // Since we start at the root, the starting min and max values are the root's value
34 dfs(root, root.val, root.val);
35
36 // After traversing the tree, return the global maxDifference found
37 return maxDifference;
38}
39
Time and Space Complexity
The given Python function maxAncestorDiff
computes the maximum difference between the values of any two nodes with an ancestor/descendant relationship in a binary tree.
Time Complexity:
The time complexity of the function is O(N)
, where N
is the number of nodes in the binary tree. This is because the function performs a depth-first search (DFS), visiting each node exactly once. During each visit, it performs a constant amount of work by updating the minimum and maximum values encountered so far and comparing them to the current node's value.
Space Complexity:
The space complexity of the function is O(H)
, where H
is the height of the binary tree. This complexity comes from the call stack used for recursion during DFS. In the worst case of a skewed tree, where the tree takes the form of a linked list (either every node has only a right child or only a left child), the height H
would be equal to N
, leading to a worst-case space complexity of O(N)
. For a balanced tree, the space complexity would be O(log N)
, as the height H
would be logarithmic in the number of nodes N
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node