medium Maximum Difference Between Node and Ancestor

Problem Statement

You are given the root of a binary tree. Each node in the tree has a unique value.

Find the maximum difference between the value of any node and the value of any ancestor of that node.

An ancestor of a node is any node on the path from the root to that node, excluding the node itself.

Examples

Example 1:

• Input: [5, 3, 8, 1, 4, null, 10]

    5
   / \
  3   8
 / \   \
1   4  10

• Output: 5
• Explanation: The maximum difference is between node 10 and its ancestor node 5 (|10 - 5| = 5).

Example 2:

• Input: [10, 6, 15, 4, 8, 12, 18]

   10
   /  \
  6   15
 /\   / \
4  8  12 18

• Output: 8
• Explanation: The maximum difference is between node 18 and its ancestor node 10 (|18 - 10| = 8).

Example 3:

• Input: [8,3,10,1,6,null,14,null,null,4,7,13]

    8
   / \
  3   10
 / \   \
1   6   14
   /\   /
  4  7 13

• Output: 7
• Explanation: The maximum difference is between node 1 and its ancestor node 8 (|8 - 1| = 7).

Constraints:

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

Solution

To solve this problem, we need to traverse the binary tree and at each node, keep track of the minimum and maximum values encountered from the root to that node. This way, for each node, we can calculate the potential maximum difference between the node's value and the minimum and maximum values seen so far in its path. By comparing these differences for all nodes, we can find the overall maximum difference.

This approach is effective because it ensures that we consider all possible ancestor-descendant pairs. We use a recursive function to traverse the tree and pass along the minimum and maximum values seen so far. This avoids the need for a separate traversal to gather ancestor values, thus making the solution efficient.

Step-by-step Algorithm

1. Initialize Variables:

   • Create a helper function that takes a node, the current minimum value, and the current maximum value as parameters.

2. Base Case:

   • If the current node is null, return the difference between the maximum value and the minimum value.

3. Update Minimum and Maximum Values:

   • Update the current minimum value to be the smaller of the current minimum value and the current node’s value.
   • Update the current maximum value to be the larger of the current maximum value and the current node’s value.

4. Recursive Calls:

   • Recursively call the helper function for the left child of the current node.
   • Recursively call the helper function for the right child of the current node.

5. Calculate Differences:

   • Calculate the maximum difference for the left subtree.
   • Calculate the maximum difference for the right subtree.

6. Return the Maximum Difference:

   • Return the larger of the two differences calculated in the previous step.

Algorithm Walkthrough

Let's walk through the algorithm step-by-step for the input tree [10, 6, 15, 4, 8, 12, 18].

1. Start with the root node (10):

   • Initial min value = 10, max value = 10.
   • Call helper on left child (6) and right child (15).

2. Traverse to the left child (6):

   • Current node = 6, min value = 6, max value = 10.
   • Call helper on left child (4) and right child (8).

3. Traverse to the left child (4):

   • Current node = 4, min value = 4, max value = 10.
   • Call helper on left child (null) and right child (null).
   • Both children are null, return max - min = 10 - 4 = 6.

4. Traverse to the right child (8):

   • Current node = 8, min value = 6, max value = 10.
   • Call helper on left child (null) and right child (null).
   • Both children are null, return max - min = 10 - 6 = 4.

5. Return to node (6):

   • Maximum difference from left subtree = 6 (from node 4).
   • Maximum difference from right subtree = 4 (from node 8).
   • Maximum difference at node 6 = max(6, 4) = 6.

6. Traverse to the right child (15):

   • Current node = 15, min value = 10, max value = 15.
   • Call helper on left child (12) and right child (18).

7. Traverse to the left child (12):

   • Current node = 12, min value = 10, max value = 15.
   • Call helper on left child (null) and right child (null).
   • Both children are null, return max - min = 15 - 10 = 5.

8. Traverse to the right child (18):

   • Current node = 18, min value = 10, max value = 18.
   • Call helper on left child (null) and right child (null).
   • Both children are null, return max - min = 18 - 10 = 8.

9. Return to node (15):

   • Maximum difference from left subtree = 5 (from node 12).
   • Maximum difference from right subtree = 8 (from node 18).
   • Maximum difference at node 15 = max(5, 8) = 8.

10. Return to root node (10):

    • Maximum difference from left subtree = 6 (from node 6).
    • Maximum difference from right subtree = 8 (from node 15).
    • Maximum difference at root node = max(6, 8) = 8.

The maximum difference between a node and its ancestor in this tree is 8.

Code

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

class Solution {

  // Main function to find the maximum difference between node and ancestor
  public int maxAncestorDiff(TreeNode root) {
    return helper(root, root.val, root.val);
  }

  // Helper function to traverse the tree and calculate min and max values
  private int helper(TreeNode node, int minVal, int maxVal) {
    // If the node is null, return the difference between max and min values
    if (node == null) {
      return maxVal - minVal;
    }
    // Update min and max values
    minVal = Math.min(minVal, node.val);
    maxVal = Math.max(maxVal, node.val);
    // Recursively find the max difference in left and right subtrees
    int leftDiff = helper(node.left, minVal, maxVal);
    int rightDiff = helper(node.right, minVal, maxVal);
    // Return the maximum of left and right differences
    return Math.max(leftDiff, rightDiff);
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    TreeNode root1 = new TreeNode(5);
    root1.left = new TreeNode(3);
    root1.right = new TreeNode(8);
    root1.left.left = new TreeNode(1);
    root1.left.right = new TreeNode(4);
    root1.right.right = new TreeNode(10);
    System.out.println(sol.maxAncestorDiff(root1)); // Output: 5

    TreeNode root2 = new TreeNode(10);
    root2.left = new TreeNode(6);
    root2.right = new TreeNode(15);
    root2.left.left = new TreeNode(4);
    root2.left.right = new TreeNode(8);
    root2.right.left = new TreeNode(12);
    root2.right.right = new TreeNode(18);
    System.out.println(sol.maxAncestorDiff(root2)); // Output: 8

    TreeNode root3 = new TreeNode(8);
    root3.left = new TreeNode(3);
    root3.right = new TreeNode(10);
    root3.left.left = new TreeNode(1);
    root3.left.right = new TreeNode(6);
    root3.left.right.left = new TreeNode(4);
    root3.left.right.right = new TreeNode(7);
    root3.right.right = new TreeNode(14);
    root3.right.right.left = new TreeNode(13);
    System.out.println(sol.maxAncestorDiff(root3)); // Output: 10
  }
}

Complexity Analysis

Time Complexity

The time complexity of the solution is , where N is the number of nodes in the binary tree. This is because we perform a Depth-First Search (DFS) traversal of the tree, visiting each node exactly once.

Space Complexity

The space complexity of the solution is , where H is the height of the binary tree. This space is used by the recursive call stack. In the worst case (for a skewed tree), the height of the tree can be N, so the space complexity can be . In the average case (for a balanced tree), the height is , so the space complexity can be .