1026. Maximum Difference Between Node and Ancestor

Description

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.

Constraints

• The number of nodes in the tree is in the range [2, 5000].

• 0 <= Node.val <= 105

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : O(N) since we visit all nodes once.
 * Space complexity : O(N) since we need stacks to do recursion, and the 
 *    maximum depth of the recursion is the height of the tree, which is O(N) 
 *    in the worst case and O(log(N)) in the best case.
 */

class Solution {
    public int maxAncestorDiff(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return dfs(root, root.val, root.val);
    }
    
    private int dfs(TreeNode node, int min, int max) {
        if(node == null) {
            return max-min;
        }
        if(node.val < min) {
            min = node.val;
        }
        if(node.val > max) {
            max = node.val;
        }
        return Math.max(dfs(node.left, min, max), dfs(node.right, min, max));
    }
}

Follow up