Maximum Difference Between Node and Ancestor

Explore Solutions in Other Languages

Problem Description

Welcome to the world of binary trees, where every node is a potential ancestor, and every child is just waiting to disappoint you with their life choices! The problem at hand is to find the maximum difference between a node and its ancestor in a binary tree.

Imagine you’re at a family reunion, and you discover that your great-great-grandfather was a millionaire, while your cousin is still living in your parents’ basement. The goal is to find the biggest financial gap between any ancestor and their descendants. In programming terms, this translates to finding the maximum difference between the values of any node and its ancestors in a binary tree.

So, if you have a tree that looks like this:

The maximum difference would be between the root (8) and the leaf (1), which is 7.

Code Solution


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

  // Returns |the maximum - the minimum| of the tree.
  private int maxAncestorDiff(TreeNode root, int mn, int mx) {
    if (root == null)
      return 0;
    mn = Math.min(mn, root.val);
    mx = Math.max(mx, root.val);
    final int l = maxAncestorDiff(root.left, mn, mx);
    final int r = maxAncestorDiff(root.right, mn, mx);
    return Math.max(mx - mn, Math.max(l, r));
  }
}

Approach Explanation

The approach used in the code is a recursive depth-first search (DFS) that traverses the binary tree. The function maxAncestorDiff takes three parameters: the current node, the minimum value encountered so far, and the maximum value encountered so far.

If the current node is null, it returns 0 (base case).
It updates the minimum and maximum values based on the current node’s value.
It recursively calls itself for the left and right children of the current node.
Finally, it calculates the maximum difference between the maximum and minimum values found during the traversal.

Time and Space Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack.

Real-World Example

Think of a family tree where your great-grandparents were wealthy landowners, and your parents are just trying to make ends meet. The maximum difference in wealth between any ancestor and their descendants can be likened to the maximum difference in values between nodes in a binary tree. Just like in life, some branches of the family tree flourish while others wither away!