# Employment Tree
###### tags: `Divide and Conquer`, `Tree`, `Amazon OA`

Description:
Imagine that an employment tree represents the formal employee hierarchy at Amazon. Manager nodes have chid nodes for each employee that reports to them; each of these employees can, in turn, have child nodes representing their respective reportees. Each node in the tree contains an integer representing the number of months the employee has spent at the company.

Team tenure is computed as the average tenure of the manager and all the company employees working below the manager. The oldest team has the highest team tenure.

Write an algorithm to find the manager of the team with the highest tenure. An employee must have child nodes
to be a manager.

**Input**
The input to the function/method consists of an argument -
president, a node representing the root node of the employee hierarchy.

**Output**
Return the node which has the oldest team.

**Note**
There will be at least one child node in the tree and there will be no ties.

Solution:

public class EmploymentTree {
    /**
     * public class TreeNode {
     *     List<TreeNode> children;
     *     int val;
     *     public TreeNode(int val) {
     *         this.val = val;
     *         this.children = new ArrayList<>();
     *     }
     * }
     */
    private class Result {
        int totalNodes;
        int totalValues;
        double average;
        TreeNode maxNode;
        double maxAverage;

        public Result(int totalNodes, int totalValues, double average, TreeNode maxNode, double maxAverage) {
            this.totalNodes = totalNodes;
            this.totalValues = totalValues;
            this.average = average;
            this.maxNode = maxNode;
            this.maxAverage = maxAverage;
        }
    }

    public TreeNode EmploymentTree(TreeNode root) {
        return traverse(root).maxNode;
    }

    private Result traverse(TreeNode root) {
        if (root == null) {
            return null;
        }

        int sumOfNode = 1;
        int sumOfValue = root.val;
        double maxAverage = 0;
        TreeNode maxNode = null;
        for (TreeNode child : root.children) {
            Result r = traverse(child);
            if (r == null) {
                continue;
            }

            if (maxAverage < r.maxAverage) {
                maxAverage = r.maxAverage;
                maxNode = r.maxNode;
            }

            sumOfNode += r.totalNodes;
            sumOfValue += r.totalValues;
        }

        double average = (double)sumOfValue / sumOfNode;
        if (sumOfNode > 1 && average > maxAverage) {
            maxAverage = average;
            maxNode = root;
        }

        return new Result(sumOfNode, sumOfValue, average, maxNode, maxAverage);
    }