Domain 2MediumMEDIUM

Maximum Difference Between Node and Ancestor

Use Depth-First Search to traverse the tree while maintaining the minimum and maximum values seen on the current path from the root, calculating differences at each step.

Domain: medium•Updated: 2026-09-06
#DFS#Binary Tree#O(N)#Space O(H)

Problem Breakdown

We are given a binary tree where we need to find the largest absolute difference between any two nodes such that one is an ancestor of the other. Inputs: root (the root node of a Binary Tree).
Outputs: An integer representing the maximum value V=∣A.val−B.val∣V = |A.val - B.val|.

Intuition

The problem requires comparing every descendant with all its ancestors on the path from the root to that descendant. A naive approach would traverse up for each node, leading to O(N2)O(N^2) time complexity in skewed trees. Key Insight: During a Depth-First Search (DFS), we can maintain two values along the current recursion stack: min_val and max_val, representing the minimum and maximum node values encountered on the path from the root to the current node’s parent. For any current node, its ancestors’ values are implicitly bounded by these min/max limits. The difference between the current node and any ancestor is maximized when compared against either the smallest or largest value seen so far in that branch.

Approach

  1. Initialize a variable to track the global maximum difference found (max_diff).
  2. Define a recursive helper function dfs(node, min_val, max_val).
  3. Base Case: If node is null, return immediately (end of path).
  4. Calculate Difference: Compute absolute differences between current node’s value and the passed min_val/max_val. Update global maximum if a larger difference is found. Note: Comparing with itself yields 0, which does not affect the maximum unless all values are identical.
  5. Recurse: Pass updated bounds to children (min(min_val, node.val), max(max_val, node.val)). This ensures descendants compare against ancestors including themselves (which is valid for path logic as they become part of the ancestor chain for their own children).
  6. Start DFS from root with initial bounds set to root.val itself so that its immediate children calculate differences correctly relative to it.

Complexity Analysis

  • Time Complexity: O(N)O(N) where N is the number of nodes. Each node is visited exactly once during the traversal, and constant time operations are performed at each step.
  • Space Complexity: O(H)O(H) for the recursion stack space, where H is the height of the tree. In a balanced tree this is O(log⁡N)O(\log N). In a skewed tree (worst case), it degrades to O(N)O(N). Python’s default recursion limit may need adjustment for very deep trees (N=5000N=5000) in local environments, though LeetCode typically configures limits higher.

Solution

import sys

# Increase recursion depth just in case of skewed tree on strict environments
sys.setrecursionlimit(10**4 + 200) 

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:
        # Initialize global maximum difference. 
        # Since values are non-negative and we need different nodes (though diff 0 is valid),
        # start with a safe lower bound or handle first node logic inside DFS.
        self.max_diff = 0
        
        def dfs(node, min_val, max_val):
            if not node:
                return
            
            # Calculate difference between current node and the bounds of its ancestors
            diff1 = abs(min_val - node.val)
            diff2 = abs(max_val - node.val)
            
            # Update global maximum found so far
            self.max_diff = max(self.max_diff, diff1, diff2)
            
            # Pass updated min/max to children. 
            # The current node becomes part of the path for its descendants.
            dfs(node.left, min(min_val, node.val), max(max_val, node.val))
            dfs(node.right, min(min_val, node.val), max(max_val, node.val))

        # Start DFS from root with initial bounds set to root's value itself.
        if root:
            dfs(root, root.val, root.val)
            
        return self.max_diff

Edge Cases Handled

  • Skewed Tree: The recursion handles deep trees by maintaining stack depth proportional to height; logic remains O(N)O(N) regardless of shape. Added sys.setrecursionlimit for safety against default Python limits on skewed inputs near N=5000.
  • Single Path (Line): Works correctly as min and max propagate down the single chain, calculating differences at each step against all previous nodes implicitly via bounds.
  • Identical Values: If a subtree has identical values, diffs are 0; logic handles this naturally without special checks since we maximize over absolute differences (initialized to 0).
  • Initialization: The bounds are passed as (root.val, root.val). This ensures that for any child of the root, both ancestors (the path from root down) start with root’s value in mind before updating to include children’s values.