Vultr DocsLatest Content

Maximum Difference Between Node and Ancestor

Updated on 12 June, 2025
Maximum Difference Between Node and Ancestor header image

Problem Statement

Given the root node of a binary tree, our goal is to determine the maximum absolute difference between the values of two nodes whereby one node is an ancestor of the other. An ancestor node in this context refers to a node from which you can reach another node (descendant) by traveling downwards through the tree, potentially spanning multiple levels.

Examples

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

Approach and Intuition

To solve the problem of finding the maximum absolute difference between ancestor and descendant nodes in a binary tree, we can utilize a recursive depth-first search (DFS). This approach leverages the tree's hierarchical structure, allowing us to compute values while exploring each node and its subtree. Here's a step-by-step breakdown of the intuition and method:

  1. Start the DFS from the root node of the tree. For each node, consider it as a potential ancestor.
  2. As we traverse to the children (left and right) of the current node, we calculate the absolute difference between the current ancestor's value and the current descendant's value.
  3. Track the maximum of these differences as we dive deeper into the tree.
  4. For each subtree rooted at a current node, return the minimum and maximum values found in the subtree to the above layers. This helps in efficiently calculating the absolute differences with higher-up ancestors without the need for repetitive comparisons.
  5. The recursion ensures that every node in the tree is considered as a possible ancestor, and calculations extend down to all possible descendants in its subtree.
  6. Continue the traversal until all nodes are visited, and utilize backtracking to unwind the recursion, ensuring that all possible pairs of ancestor and descendant values are considered.

By following this approach, the algorithm ensures that the maximum difference is captured with optimal time and space complexity, governed by the depth of recursion and the tree's size.

Solutions

  • Java
  • Python
java 
class Solution {
    public int findMaxDifference(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return search(root, root.val, root.val);
    }

    public int search(TreeNode current, int maximum, int minimum) {
        if (current == null) {
            return maximum - minimum;
        }
        maximum = Math.max(maximum, current.val);
        minimum = Math.min(minimum, current.val);
        int diffLeft = search(current.left, maximum, minimum);
        int diffRight = search(current.right, maximum, minimum);
        return Math.max(diffLeft, diffRight);
    }
}

In the problem of finding the maximum difference between a node and its ancestor in a binary tree, the Java implementation employs a recursive approach to traverse the tree and compute the difference. Here's a breakdown of how the given solution works:

The main method, findMaxDifference, initiates the recursive search by passing the root node along with its value as both the initial maximum and minimum values. This is because, at the beginning, the root is compared to itself.

Within the recursive method search, check if the current node is null. If it is, return the difference maximum - minimum which represents the computed difference for that path in the tree.

If the current node is not null:

  • Update the maximum by taking the higher value between the current maximum and the node’s value.
  • Update the minimum by choosing the lower value between the current minimum and the node’s value.

Recurse down to the left child and the right child of the current node:

  • Calculate the difference for the left subtree by calling search with current.left, and passing the updated maximum and minimum.
  • Similarly, compute the difference for the right subtree.

Finally, the maximum difference for the current node is determined by taking the larger value between the differences returned from the left and right child computations.

The approach efficiently calculates the necessary maximum difference using a depth-first search (DFS), with each node invoking two recursive calls — one for each child — ensuring each path down the tree is explored.

python 
class Solution:
    def maximumAncestorDifference(self, root: TreeNode) -> int:
        if root is None:
            return 0

        def traverse(node, highest, lowest):
            if node is None:
                return highest - lowest
            highest = max(highest, node.val)
            lowest = min(lowest, node.val)
            difference_left = traverse(node.left, highest, lowest)
            difference_right = traverse(node.right, highest, lowest)
            return max(difference_left, difference_right)

        return traverse(root, root.val, root.val)

The provided Python code implements a solution for finding the maximum difference between a node and its ancestors in a binary tree. Follow these steps for Python implementation:

  1. Define the maximumAncestorDifference function within the Solution class, which takes the root of a binary tree as its input.
  2. Begin by checking if the root is None. If true, return 0 as there are no nodes to calculate the difference for.
  3. Proceed with a nested helper function, traverse, which is used to explore each node in the tree. traverse takes three parameters:
    • node: the current node being processed.
    • highest: the maximum value found in the current path from the root to the current node.
    • lowest: the minimum value found in the current path.
  4. In the traverse function, check if the current node is None. If it is, return the difference between the highest and lowest values found since it marks the end of a branch.
  5. Update the highest and lowest variables as the maximum and minimum between the current node's value and the previously recorded values respectively.
  6. Recurse through the left and right children of the current node, capturing the differences from these subtrees.
  7. The result from traverse is the maximum of the difference values returned by the left and right subtree traversals.
  8. Finally, the maximum difference found for the entire tree is returned by the traverse function initialized with the root.

This approach ensures the efficient computation of the maximum difference between any node and an ancestor by leveraging depth-first search through recursion.

Comments

No comments yet.