Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximum Difference Between Node and Ancestor solution and explanation

MediumBinary TreeDepth-First SearchTree6 min read78.1% acceptanceUpdated 9 Apr 2026
Asked atJosh TechnologyEPAM SystemsAmazonMetaBloomberg
Practise Maximum Difference Between Node and Ancestor
6:09
Maximum Difference Between Node and Ancestor | Live Coding with Explanation | Leetcode #1026Algorithms Made Easy · 6:09 · 9K viewsWatch on YouTube
9 more videos on this problem
  1. Maximum Difference Between Node and Ancestor | Live Coding with Explanation | Leetcode #1026Algorithms Made Easy · 6:09 · 9K views
  2. 1026. Maximum Difference Between Node and AncestorAryan Mittal · 10:31 · 2K views
  3. Maximum Difference Between Node and Ancestor | Leet code 1026 | Theory explained + Python codeSai Anish Malla · 15:40 · 2K views
  4. LeetCode 1026. Maximum Difference Between Node and AncestorHappy Coding · 13:12 · 1K views
  5. Leetcode Solution - 1026 Maximum Difference Between Node and AncestorJohn Leonardo · 6:03 · 1K views
  6. Node and Ancestor Maximum Difference (Leetcode 1026)Algorithms Casts · 16:17 · 791 views
  7. Leetcode 1026 Maximum Difference Between Node and AncestorRen Zhang · 7:34 · 764 views
  8. Maximum Difference Between Node and Ancestor - 9th Nov LeetCode - GoMaster Coding InterviewsGoMaster Coding Interviews · 9:45 · 454 views
  9. Maximum Difference Between Node and Ancestor - Two Solutions - Trees - PythonCheatCode Ninja · 13:11 · 382 views
  10. 1026. Maximum Difference Between Node and Ancestor | English | MediumSimple Code - 단순코드 · 13:28 · 368 views

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

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 overview

Problem Overview: You are given the root of a binary tree. For any node, an ancestor is any node on the path from the root to that node. The task is to compute the maximum value of |ancestor.val - node.val| across all such pairs in the tree.

Approach 1: Depth First Search with Min/Max Tracking (Time: O(n), Space: O(h))

This is the optimal strategy and the one most interviewers expect. Traverse the tree using DFS while carrying two values along the path: the minimum value and maximum value seen from the root to the current node. At each step, update the answer using max(abs(node.val - minVal), abs(node.val - maxVal)). Then update the running minVal and maxVal before exploring children. Every node is processed once, so the time complexity is O(n), where n is the number of nodes. The recursion stack uses O(h) space where h is the tree height. This approach works because the largest difference for a node must come from either the smallest or largest ancestor value along its path.

This technique is a classic pattern when working with tree traversal problems. Instead of storing the entire ancestor list, you keep only the extremes needed to compute the maximum difference.

Approach 2: Breadth First Search (Iterative) (Time: O(n), Space: O(n))

You can also solve the problem using an iterative BFS with a queue. Each queue entry stores a tuple: (node, minVal, maxVal). Start with the root where both values equal root.val. For every node popped from the queue, compute the difference with the tracked min and max, update the global answer, then push children with updated ranges. The logic mirrors the DFS solution but replaces recursion with an explicit queue.

This approach also processes every node exactly once, giving O(n) time complexity. However, the queue can grow to the width of the tree, so the space complexity becomes O(n) in the worst case. BFS is useful if you prefer iterative solutions or want to avoid recursion depth issues.

Both methods rely on the same insight: the maximum difference at a node depends only on the minimum and maximum values seen among its ancestors. The traversal simply propagates those values while exploring the tree using either Depth-First Search or level-order traversal on a Binary Tree.

Recommended for interviews: Use the DFS min/max tracking approach. It is concise, runs in O(n) time with O(h) space, and clearly demonstrates understanding of recursive tree traversal. Mentioning the BFS alternative shows deeper understanding, but the DFS version is typically the cleanest implementation during interviews.

Approach 1: Depth First Search with Min/Max Tracking

This approach leverages Depth First Search (DFS) to explore the binary tree. The key idea is to maintain the minimum and maximum values observed along the path from the root to the current node. By comparing the current node's value with these min/max values, we can compute potential maximum differences. As we backtrack, we use these values to determine the maximum difference possible for subtree paths.

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:
        def dfs(node, min_val, max_val):
            if not node:
                return max_val - min_val
            min_val = min(min_val, node.val)
            max_val = max(max_val, node.val)
            left_diff = dfs(node.left, min_val, max_val)
            right_diff = dfs(node.right, min_val, max_val)
            return max(left_diff, right_diff)
        return dfs(root, root.val, root.val)
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }
    
    private int dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) return maxVal - minVal;
        minVal = Math.min(minVal, node.val);
        maxVal = Math.max(maxVal, node.val);
        int leftDiff = dfs(node.left, minVal, maxVal);
        int rightDiff = dfs(node.right, minVal, maxVal);
        return Math.max(leftDiff, rightDiff);
    }
}
#include <algorithm>
#include <limits.h>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        return dfs(root, root->val, root->val);
    }
    
    int dfs(TreeNode* node, int minVal, int maxVal) {
        if (!node) return maxVal - minVal;
        minVal = std::min(minVal, node->val);
        maxVal = std::max(maxVal, node->val);
        int leftDiff = dfs(node->left, minVal, maxVal);
        int rightDiff = dfs(node->right, minVal, maxVal);
        return std::max(leftDiff, rightDiff);
    }
};
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val);
    this.left = (left===undefined ? null : left);
    this.right = (right===undefined ? null : right);
}

var maxAncestorDiff = function(root) {
    var dfs = function(node, minVal, maxVal) {
        if (node === null) return maxVal - minVal;
        minVal = Math.min(minVal, node.val);
        maxVal = Math.max(maxVal, node.val);
        let leftDiff = dfs(node.left, minVal, maxVal);
        let rightDiff = dfs(node.right, minVal, maxVal);
        return Math.max(leftDiff, rightDiff);
    };
    return dfs(root, root.val, root.val);
};
#include <stdio.h>
#include <stdlib.h>

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

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

int maxAncestorDiff(struct TreeNode* root) {
    if (root == NULL) return 0;
    return maxAncestorDiffHelper(root, root->val, root->val);
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int MaxAncestorDiff(TreeNode root) {
        return Dfs(root, root.val, root.val);
    }

    private int Dfs(TreeNode node, int minVal, int maxVal) {
        if (node == null) return maxVal - minVal;
        minVal = Math.Min(minVal, node.val);
        maxVal = Math.Max(maxVal, node.val);
        int leftDiff = Dfs(node.left, minVal, maxVal);
        int rightDiff = Dfs(node.right, minVal, maxVal);
        return Math.Max(leftDiff, rightDiff);
    }
}

The Python implementation makes use of a nested function dfs, focusing on recursion and maintaining path min/max values to discover maximum differences.

Complexity

Time Complexity: O(n), traveling each node once.
Space Complexity: O(h), stack height of tree depth.

Try this approach in the editor

Approach 2: Breadth First Search (Iterative)

This approach utilizes an iterative Breadth First Search (BFS) paradigm using a queue to traverse the tree. Queue elements consist of a node and associated min/max values for the path leading to this node. As nodes are processed, the difference between node values and min/max path values are calculated to find the maximum difference.

from collections import deque

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        if not root:
            return 0
        max_diff = 0
        queue = deque([(root, root.val, root.val)])
        while queue:
            node, min_val, max_val = queue.popleft()
            max_diff = max(max_diff, abs(node.val - min_val), abs(node.val - max_val))
            min_val, max_val = min(min_val, node.val), max(max_val, node.val)
            if node.left:
                queue.append((node.left, min_val, max_val))
            if node.right:
                queue.append((node.right, min_val, max_val))
        return max_diff

In this solution, a queue is used for BFS traversal, storing node and path min/max values. For each node, we compute current possible differences and keep track of the maximum difference encountered. The solution efficiently processes tree traversal iteratively.

Complexity

Time Complexity: O(n), as each node is visited once.
Space Complexity: O(n), for the queue storing the nodes in the worst case (when the tree is bushy).

Try this approach in the editor

Approach 3: DFS

For each node, to find the maximum difference with its ancestor nodes, we only need to find the difference between the maximum and minimum values of the ancestor nodes. The maximum difference among all nodes and their ancestor nodes is the answer.

Therefore, we design a function dfs(root, mi, mx), where the current node being searched is root, the maximum value of its ancestor nodes is mx, and the minimum value is mi. The function updates the maximum difference ans.

The logic of the function dfs(root, mi, mx) is as follows:

  • If root is null, return directly.
  • Otherwise, we update ans = max(ans, |mi - root.val|, |mx - root.val|).
  • Then update mi = min(mi, root.val), mx = max(mx, root.val), and recursively search the left and right subtrees.

In the main function, we call dfs(root, root.val, root.val), and finally return ans.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxAncestorDiff(root: TreeNode | null): number {
    const dfs = (root: TreeNode | null, mi: number, mx: number): void => {
        if (!root) {
            return;
        }
        ans = Math.max(ans, Math.abs(root.val - mi), Math.abs(root.val - mx));
        mi = Math.min(mi, root.val);
        mx = Math.max(mx, root.val);
        dfs(root.left, mi, mx);
        dfs(root.right, mi, mx);
    };
    let ans: number = 0;
    dfs(root, root.val, root.val);
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxAncestorDiff(root *TreeNode) (ans int) {
	var dfs func(*TreeNode, int, int)
	dfs = func(root *TreeNode, mi, mx int) {
		if root == nil {
			return
		}
		ans = max(ans, max(abs(mi-root.Val), abs(mx-root.Val)))
		mi = min(mi, root.Val)
		mx = max(mx, root.Val)
		dfs(root.Left, mi, mx)
		dfs(root.Right, mi, mx)
	}
	dfs(root, root.Val, root.Val)
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Depth First Search with Min/Max Tracking

Time Complexity: O(n), traveling each node once.
Space Complexity: O(h), stack height of tree depth.

Breadth First Search (Iterative)

Time Complexity: O(n), as each node is visited once.
Space Complexity: O(n), for the queue storing the nodes in the worst case (when the tree is bushy).

DFS–

Complexity analysis

ApproachTimeSpaceWhen to Use
DFS with Min/Max TrackingO(n)O(h)Best general solution. Clean recursive logic and optimal memory for balanced trees.
Iterative BFS with Range TrackingO(n)O(n)Useful when avoiding recursion or when implementing level-order traversal iteratively.

Frequently asked questions

Is Maximum Difference Between Node and Ancestor easy or hard?

Maximum Difference Between Node and Ancestor is rated Medium on LeetCode. The difficulty comes from recognizing that you only need the minimum and maximum ancestor values rather than storing all ancestors.

Maximum Difference Between Node and Ancestor Python/Java solution

Both Python and Java implementations follow the same idea: pass the current path's minimum and maximum values during DFS. Update the result at each node and recursively explore left and right children. The algorithm remains O(n) regardless of language.

How to solve Maximum Difference Between Node and Ancestor in O(n)?

Traverse the tree using DFS while carrying the minimum and maximum ancestor values seen so far. For each node, update the result using the difference between the node value and those extremes. Then propagate updated min and max values to child nodes. Each node is processed once, giving O(n) time complexity.

What is the best approach for Maximum Difference Between Node and Ancestor?

Depth First Search with min/max tracking is the most efficient approach. While traversing from root to leaves, keep track of the smallest and largest values seen on the path. At each node compute the difference with these values. This processes each node once for an O(n) time solution.

Is Maximum Difference Between Node and Ancestor asked at Google/Amazon/Meta?

Binary tree DFS problems like this frequently appear in interviews at companies such as Amazon, Google, Meta, and Microsoft. The question tests recursive traversal, maintaining state along a path, and reasoning about ancestor relationships in trees.

What data structure is used in Maximum Difference Between Node and Ancestor?

The core data structure is a binary tree. The solution typically uses Depth-First Search recursion with variables that track the minimum and maximum ancestor values along the current path. An alternative implementation uses a queue for BFS.

What is the time complexity of Maximum Difference Between Node and Ancestor?

The optimal solution runs in O(n) time because every node in the binary tree is visited exactly once during traversal. The DFS approach uses O(h) space for the recursion stack, where h is the height of the tree.

Comments

Now write it yourselfClose this page and solve Maximum Difference Between Node and Ancestor in the editor, without looking.
Practise Maximum Difference Between Node and Ancestor