We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Difference Between Node and Ancestor

Number: 1092

Difficulty: Medium

Paid? No

Companies: EPAM Systems, Amazon, Meta, Apple

Problem Description

Given the root of a binary tree, determine the maximum difference v between the values of any two nodes such that one node is an ancestor of the other. An ancestor is defined such that it is either a direct parent or any node in the path from the root to that node.

Key Insights

  • Use Depth-First Search (DFS) to traverse the tree.
  • Track the minimum and maximum values encountered along the current path from the root.
  • At each node, update the global maximum difference using the current node’s value and the tracked minimum and maximum.
  • The solution leverages recursion which implicitly uses the call stack to manage state.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(h), where h is the height of the tree. In the worst case (skewed tree) this could be O(n).

Solution

The problem can be solved using a DFS traversal that passes along two values: the current minimum and maximum encountered on the path from the root to the current node. At each node, compute the potential differences from the current node’s value with both the minimum and maximum. Update the overall maximum difference if these values yield a larger difference. Then, update the current path’s minimum and maximum values, and recursively traverse the left and right children. When the traversal backtracks, the previously computed values guarantee the differences are correctly calculated for all ancestor-descendant relations.

Code Solutions

# 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: TreeNode) -> int:
        # Helper function for DFS traversal with current min and max values.
        def dfs(node, cur_min, cur_max):
            if not node:
                # At a null node, return the difference encountered so far.
                return cur_max - cur_min
            # Update the current path's min and max values.
            cur_min = min(cur_min, node.val)
            cur_max = max(cur_max, node.val)
            # Recursively get the maximum difference in both subtrees.
            left_diff = dfs(node.left, cur_min, cur_max)
            right_diff = dfs(node.right, cur_min, cur_max)
            # Return the maximum difference found.
            return max(left_diff, right_diff)
        
        # Start DFS with the root value as both current min and max.
        return dfs(root, root.val, root.val)
← Back to All Questions