Problem Link - Family Tree
Problem Statement:
You are given a family tree with N members numbered 1 ... N. Every person i, except for the founder of the family (root) has a parent denoted by P[i]. P[root] = -1 by definition. Person i is a descendant of person j if i belongs to the subtree rooted at j.
The net worth (adjusted for inflation) is given for all the members of the family. Your task is to find the maximum difference in net worth’s of two members where one member is a descendant of the other.
You can assume that no two members of this family married each other. So it remains a “family tree”.
Approach:
To solve this, we perform a depth-first traversal (DFS) starting from the root of the tree. For each node, we calculate the minimum and maximum net worth in its subtree by recursively processing its children. During this traversal, we also compute the maximum difference in net worth between the current node and any of its descendants. At each node, the current node’s value is compared with the minimum and maximum values found in its children’s subtrees, and the maximum difference is updated accordingly. The result is the largest difference observed during the traversal.
Time Complexity:
The time complexity is O(N) because each node and its edges are processed once during the DFS traversal.
Space Complexity:
The space complexity is O(N) due to the storage required for the tree structure and the recursive call stack.