1026. Maximum Difference Between Node and Ancestor

MediumTreeDepth-First SearchBinary Tree
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of these properties could exist for a graph but not a tree?

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:

  1. Define a recursive helper function dfs(root, mi, mx) that will be used for DFS traversal of the tree.
  2. If the current root is None, which means we've reached a leaf node's child, we return, as there are no more nodes to process in this path.
  3. The helper function is designed to continuously update a nonlocal variable ans, which holds the maximum absolute difference found.
  4. At each node, we compare and update ans with the absolute difference of the current node's value root.val with both the minimum (mi) and maximum (mx) values seen so far along the path from the root.
  5. We perform this comparison using max(ans, abs(mi - root.val), abs(mx - root.val)).
  6. After updating ans, we also update mi and mx for the recursive calls on the children nodes, setting mi to min(mi, root.val) and mx to max(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.
  7. Recursive calls are then made to continue the DFS traversal on the left child dfs(root.left, mi, mx) and the right child dfs(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

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

  1. The dfs function is first called with root.val = 8, mi = 8, mx = 8. We are at the root.

  2. Explore left child (3). Call dfs(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

  3. Go down to the left child of 3, node 1. Call dfs(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.

  4. The other child of 3 is 6. Call dfs(6, min(3,6), max(8,6)):

    • mi = 3, mx = 8.
    • Update answer:
      • max(7, abs(3 - 6), abs(8 - 6))
      • ans remains 7.

  5. Node 6 has a left child 4. Call dfs(4, min(3,4), max(8,4)):

    • mi = 3, mx = 8.
    • Update answer:
      • max(7, abs(3 - 4), abs(8 - 4))
      • ans remains 7.

    Since 4 is a leaf node, we go back up.

  6. Node 6 also has right child 7. Call dfs(7, min(3,7), max(8,7)):

    • mi = 3, mx = 8.
    • Update answer:
      • max(7, abs(3 - 7), abs(8 - 7))
      • ans remains 7.

    Node 7 is also a leaf; traverse back up to 3, then to 8.

  7. Now explore right child (10) of the root. Call dfs(10, min(8,10), max(8,10)):

    • mi = 8, mx = 10.
    • Update answer:
      • max(7, abs(8 - 10), abs(10 - 8))
      • ans remains 7.

  8. Node 10 has right child 14. Call dfs(14, min(8,14), max(10,14)):

    • mi = 8, mx = 14.
    • Update answer:
      • max(7, abs(8 - 14), abs(14 - 8))
      • ans becomes 14 - 8 = 6 but since our current ans = 7, there is no update.

  9. Node 14 has a left child 13. Call dfs(13, min(8,13), max(14,13)):

    • mi = 8, mx = 14.
    • Update answer:
      • max(7, abs(8 - 13), abs(14 - 13))
      • ans remains 7 because the differences 5 and 1 are smaller than the current ans.

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
Not Sure What to Study? Take the 2-min Quiz๏ผš

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Everything About Trees

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

DFS Fundamentals

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

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ