Maximum Difference Between Node and Ancestor - Video Solutions

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.