medium Maximum Difference Between Node and Ancestor

Problem Statement

Given a root of the binary tree, return the maximum absolute difference in value between any node in a binary tree and its any ancestor.

A node a is the ancestor of node b if node a precedes node b in the path from the root to node b.

Examples

Example 1:

• Input: root = [5, 3, 8, 0, null, 4, 7, 1]

• Expected Output: 5
• Justification: The maximum difference is between node 0 and its ancestor 5, which is 5.

Example 2:

• Input: root = [2, 1, 3]

• Expected Output: 1
• Justification: There are two differences to consider: 2-1 and 3-2. Both differences are 1, so the maximum difference is 1.

Example 3:

• Input: root = [8, 2, null, 1, 5]

• Expected Output: 7
• Justification: The maximum difference is between node 1 and its ancestor 8, which is 7.

Solution

To solve this problem, we adopt a depth-first search (DFS) strategy, exploring each path from the root to the leaf nodes while keeping track of the maximum and minimum values encountered along each path. This approach is effective because it allows us to calculate the difference between the current node and its ancestors' minimum and maximum values in a single traversal, ensuring efficiency and simplicity.

The key is to update the minimum and maximum values as we move down the tree and calculate the difference at each node, comparing it with the global maximum difference found so far. This strategy is chosen for its ability to explore all possible ancestor-descendant pairs without redundant calculations or needing to store additional data structures that represent all ancestors of each node.

Step-by-step Algorithm

1. Start with the root node of the binary tree, passing the node's value as both the minimum and maximum values encountered so far to a recursive depth-first search (DFS) function.

2. DFS function:

   • If the current node is null, return the difference between the maximum and minimum values encountered so far on this path.
   • Update the minimum value if the current node's value is less than the current minimum.
   • Update the maximum value if the current node's value is greater than the current maximum.
   • Recursively call the DFS function for the left child of the current node, passing the updated minimum and maximum values.
   • Recursively call the DFS function for the right child of the current node, passing the updated minimum and maximum values.
   • Calculate the maximum difference found in the left and right subtree calls and return it.

3. Return the result of the DFS call started with the root node, which gives the maximum difference between any node and its ancestor in the binary tree.

Algorithm Walkthrough

Let's consider the input: root = [5, 3, 8, 0, null, 4, 7, 1].

Tree Structure:

The given tree can be visualized as follows:

        5
       / \
      3   8
     /   / \
    0   4   7
   /
  1

Step-by-Step Walkthrough:

1. Start at the Root (Node 5):

   • Current Node: 5
   • Current Min and Max: Both initialized to the value of the root, which is 5 (min = 5, max = 5).
   • Recursively call DFS on the left child (Node 3).

2. Move to the Left Child (Node 3):

   • Current Node: 3
   • Update Min and Max:
     • min = min(5, 3) = 3
     • max = max(5, 3) = 5
   • Recursively call DFS on the left child (Node 0).

3. Move to the Left Child (Node 0):

   • Current Node: 0
   • Update Min and Max:
     • min = min(3, 0) = 0
     • max = max(5, 0) = 5
   • Recursively call DFS on the left child (Node 1).

4. Move to the Left Child (Node 1):

   • Current Node: 1
   • Update Min and Max:
     • min = min(0, 1) = 0
     • max = max(5, 1) = 5
   • Both left and right children are null:
     • Return the difference max - min = 5 - 0 = 5.
   • Go back to the Node 0.

5. Node 0 - Right Child is Null:

   • Since the right child of Node 0 is null, the right difference is not calculated.
   • Return the maximum difference obtained from the left subtree: 5.
   • Go back to the Node 3.

6. Node 3 - Right Child is Null:

   • Since the right child of Node 3 is null, the right difference is not calculated.
   • Return the maximum difference obtained from the left subtree: 5.
   • Go back to the Node 5.

7. Move to the Right Child (Node 8):

   • Current Node: 8
   • Update Min and Max:
     • min = min(5, 8) = 5
     • max = max(5, 8) = 8
   • Recursively call DFS on the left child (Node 4).

8. Move to the Left Child (Node 4):

   • Current Node: 4
   • Update Min and Max:
     • min = min(5, 4) = 4
     • max = max(8, 4) = 8
   • Both left and right children are null:
     • Return the difference max - min = 8 - 4 = 4.
   • Go back to the Node 8.

9. Move to the Right Child (Node 7):

   • Current Node: 7
   • Update Min and Max:
     • min = min(5, 7) = 5
     • max = max(8, 7) = 8
   • Both left and right children are null:
     • Return the difference max - min = 8 - 5 = 3.
   • Go back to the Node 8.

10. Node 8 - Combine Left and Right Results:

    • Left difference: 4 (from Node 4)
    • Right difference: 3 (from Node 7)
    • Maximum difference for Node 8: max(4, 3) = 4
    • Go back to the Node 5.

11. Node 5 - Combine Left and Right Results:

    • Left difference: 5 (from Node 3's subtree)
    • Right difference: 4 (from Node 8's subtree)
    • Maximum difference for Node 5: max(5, 4) = 5

Final Output:

• The maximum difference between a node and its ancestor for the given tree [5, 3, 8, 0, null, 4, 7, 1] is 5.

Code

// Definition for a binary tree node.
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int x) { val = x; }
//     TreeNode(int x, TreeNode left, TreeNode right) {
//         this.val = x;
//         this.left = left;
//         this.right = right;
//     }
// }

public class Solution {

  // Function to find the maximum difference between node and its ancestor
  public int maxAncestorDiff(TreeNode root) {
    return dfs(root, root.val, root.val); // Start DFS with root's value as both min and max
  }

  // Helper function to perform DFS traversal
  private int dfs(TreeNode node, int min, int max) {
    if (node == null) return max - min; // Base case: return the difference between max and min
    // Update min and max values
    min = Math.min(min, node.val);
    max = Math.max(max, node.val);
    // Calculate max difference for left and right subtree
    int leftDiff = dfs(node.left, min, max);
    int rightDiff = dfs(node.right, min, max);
    // Return the maximum of left and right differences
    return Math.max(leftDiff, rightDiff);
  }

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

    // Example 1
    TreeNode example1 = new TreeNode(
      5,
      new TreeNode(3, new TreeNode(0, new TreeNode(1), null), null),
      new TreeNode(8, new TreeNode(4), new TreeNode(7))
    );
    System.out.println("Example 1:  " + solution.maxAncestorDiff(example1));

    // Example 2
    TreeNode example2 = new TreeNode(2, new TreeNode(1), new TreeNode(3));
    System.out.println("Example 2: " + solution.maxAncestorDiff(example2));

    // Example 3
    TreeNode example3 = new TreeNode(
      8,
      new TreeNode(2, new TreeNode(1), new TreeNode(5)),
      null
    );
    System.out.println("Example 3: " + solution.maxAncestorDiff(example3));
  }
}

Complexity Analysis

Time Complexity

: Where N is the number of nodes in the binary tree. The reason for this time complexity is that the depth-first search (DFS) algorithm visits each node exactly once.

Space Complexity

: Where H is the height of the binary tree. This space complexity accounts for the recursive call stack of the DFS traversal. In the worst case, if the binary tree is highly unbalanced, the height of the tree (and thus the maximum depth of the recursive call stack) could be N, making the space complexity .