Maximum Difference Between Node and Ancestor

Maximum Difference Between Node and Ancestor - Problem

Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

Input & Output

Example 1 — Basic Tree

$ Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]

› Output: 7

💡 Note: The maximum difference is between node 8 and node 1: |8 - 1| = 7. Node 8 is an ancestor of node 1.

Example 2 — Simple Tree

$ Input: root = [1,null,2,null,0,3]

› Output: 3

💡 Note: The maximum difference is between node 1 and node 3: |1 - 3| = 2, or between node 2 and node 3: |2 - 3| = 1. Actually, it's between node 1 and node 0: |1 - 0| = 1, then node 0 and node 3: |0 - 3| = 3.

Example 3 — Single Path

$ Input: root = [5,4,null,1]

› Output: 4

💡 Note: Path: 5 → 4 → 1. Maximum difference is |5 - 1| = 4.

Constraints

The number of nodes in the tree is in the range [2, 5000]
0 ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes containing integer values

Find Ancestor-Descendant Pairs

Identify all valid ancestor-descendant relationships

Calculate Maximum Difference

Find the pair with maximum absolute difference

Key Takeaway

🎯 Key Insight: Track min and max values along each path to find maximum ancestor-descendant difference in one pass

Asked in

A Amazon 12 G Google 8 M Microsoft 6

The key insight is to track the minimum and maximum values along each root-to-leaf path using DFS. The maximum difference between any ancestor-descendant pair will be the difference between the maximum and minimum values on some path. Best approach uses DFS with min/max tracking in O(n) time and O(h) space.

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Min/Max Tracking	O(n)	O(h)	Track minimum and maximum values along each root-to-leaf path
Brute Force - Check All Pairs	O(n²)	O(h)	For each node, find all its descendants and calculate differences

DFS with Min/Max Tracking — Algorithm Steps

Step 1: Start DFS from root with initial min and max as root value
Step 2: For each node, update current min and max values
Step 3: Calculate difference between current max and min
Step 4: Recursively process left and right subtrees

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with root value as both min and max

Update Min/Max

At each node, update the current path's min and max

Calculate Difference

Current difference is max - min on this path

Recurse

Continue DFS to children with updated min/max values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int dfs(struct TreeNode* node, int minVal, int maxVal) {
    if (!node) {
        return maxVal - minVal;
    }
    
    if (node->val < minVal) minVal = node->val;
    if (node->val > maxVal) maxVal = node->val;
    
    int leftDiff = dfs(node->left, minVal, maxVal);
    int rightDiff = dfs(node->right, minVal, maxVal);
    
    return leftDiff > rightDiff ? leftDiff : rightDiff;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    return dfs(root, root->val, root->val);
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // For simplicity, assume input is [8,3,10,1,6,null,14,null,null,4,7,13]
    struct TreeNode* root = createNode(8);
    root->left = createNode(3);
    root->right = createNode(10);
    root->left->left = createNode(1);
    root->left->right = createNode(6);
    root->right->right = createNode(14);
    root->left->right->left = createNode(4);
    root->left->right->right = createNode(7);
    root->right->right->left = createNode(13);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in DFS traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

98.2K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Min/Max Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler