# Sum Up Tree/Sub-Tree Values – Compute Employee Importance via DFS or BFS

You are given a data structu re of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct. Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

Example 1:
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11

Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.

Note:
One employee has at most one direct leader and may have several subordinates.
The maximum number of employees won’t exceed 2000.

The above problem can be converted equally to summing up the values of given tree and its sub trees. Almost all tree problems can be solved via DFS (Depth First Search) or BFS (Breadth First Search) algorithms.

### DFS Depth First Search

The input data is an array of tree nodes with IDs (which may not come in orders), therefore, we need to first scan the array and put them in a hash map (unordered_map) so that we can access the node by ID later.

The next is to have another hashmap e.g. cached to store the values that have been computed when navigating the tree. The C++ DFS implementation is:

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ``` ```/* // Employee info class Employee { public:     // It's the unique ID of each node.     // unique id of this employee     int id;     // the importance value of this employee     int importance;     // the id of direct subordinates     vector subordinates; }; */ class Solution { public:     int getImportance(vector employees, int id) {         for (const auto &e: employees) {             emp[e->id] = e;         }         return dfs(id);     } private:     unordered_map cached;     unordered_map emp;         int dfs(int id) {         if (emp.find(id) == emp.end()) return 0;         // we have computed this before, so no need to compute again         if (cached.find(id) != cached.end()) return cached[id];         int r = emp[id]->importance;         for (auto e: emp[id]->subordinates) {             r += dfs(e);           };         cached[id] = r; // store the value         return r;             } };```
```/*
// Employee info
class Employee {
public:
// It's the unique ID of each node.
// unique id of this employee
int id;
// the importance value of this employee
int importance;
// the id of direct subordinates
vector subordinates;
};
*/
class Solution {
public:
int getImportance(vector employees, int id) {
for (const auto &e: employees) {
emp[e->id] = e;
}
return dfs(id);
}
private:
unordered_map cached;
unordered_map emp;

int dfs(int id) {
if (emp.find(id) == emp.end()) return 0;
// we have computed this before, so no need to compute again
if (cached.find(id) != cached.end()) return cached[id];
int r = emp[id]->importance;
for (auto e: emp[id]->subordinates) {
r += dfs(e);
};
cached[id] = r; // store the value
return r;
}
};```

The DFS involves using stack, but this can be done via Recursion, which is usually easier to implement – the compiler maintains a stack i.e. calling a function is like pushing a EBP/ESP pointer to the stack.

Since the data structure is a tree. It makes sense that each node is visited at most once. Thus, we might not need a hashmap to cached the computed nodes. Here is a Java implementation that implements the Depth First Search.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ``` ```/* // Employee info class Employee {     // It's the unique id of each node;     // unique id of this employee     public int id;     // the importance value of this employee     public int importance;     // the id of direct subordinates     public List subordinates; }; */ class Solution {     public int getImportance(List employees, int id) {         Map emp = new HashMap();         for (Employee e: employees) {            emp.put(e.id, e);         }         return dfs(emp, id);     }         private int dfs(Map emp, int id) {         if (!emp.containsKey(id)) return 0;         int r = emp.get(id).importance;         for (int i: emp.get(id).subordinates) {             r += dfs(emp, i);         }         return r;     } }```
```/*
// Employee info
class Employee {
// It's the unique id of each node;
// unique id of this employee
public int id;
// the importance value of this employee
public int importance;
// the id of direct subordinates
public List subordinates;
};
*/
class Solution {
public int getImportance(List employees, int id) {
Map emp = new HashMap();
for (Employee e: employees) {
emp.put(e.id, e);
}
return dfs(emp, id);
}

private int dfs(Map emp, int id) {
if (!emp.containsKey(id)) return 0;
int r = emp.get(id).importance;
for (int i: emp.get(id).subordinates) {
r += dfs(emp, i);
}
return r;
}
}```

The BFS requires a queue. You push the root node to the queue, and its children nodes at each iteration when popping one from the queue.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 ``` ```/* // Employee info class Employee { public:     // It's the unique ID of each node.     // unique id of this employee     int id;     // the importance value of this employee     int importance;     // the id of direct subordinates     vector subordinates; }; */ class Solution { public:     int getImportance(vector employees, int id) {         for (const auto &e: employees) {             emp[e->id] = e;         }         return bfs(id);     } private:     unordered_map emp;         int bfs(int id) {         if (emp.find(id) == emp.end()) return 0;         queue Q;         Q.push(emp[id]);         int r = 0;         while (!Q.empty()) {             auto p = Q.front();             Q.pop();             r += p->importance;             for (const auto &n: p->subordinates) {                 if (emp.find(n) != emp.end()) {                     Q.push(emp[n]);                 }               }         }         return r;             } };```
```/*
// Employee info
class Employee {
public:
// It's the unique ID of each node.
// unique id of this employee
int id;
// the importance value of this employee
int importance;
// the id of direct subordinates
vector subordinates;
};
*/
class Solution {
public:
int getImportance(vector employees, int id) {
for (const auto &e: employees) {
emp[e->id] = e;
}
return bfs(id);
}
private:
unordered_map emp;

int bfs(int id) {
if (emp.find(id) == emp.end()) return 0;
queue Q;
Q.push(emp[id]);
int r = 0;
while (!Q.empty()) {
auto p = Q.front();
Q.pop();
r += p->importance;
for (const auto &n: p->subordinates) {
if (emp.find(n) != emp.end()) {
Q.push(emp[n]);
}
}
}
return r;
}
};```

The time complexity is O(N) i.e. visiting each node exactly once. The Java implementation (as a good Java coding exercise) is:

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ``` ```/* // Employee info class Employee {     // It's the unique id of each node;     // unique id of this employee     public int id;     // the importance value of this employee     public int importance;     // the id of direct subordinates     public List subordinates; }; */ class Solution {     public int getImportance(List employees, int id) {         Map emp = new HashMap();         for (Employee e: employees) {            emp.put(e.id, e);         }         if (!emp.containsKey(id)) return 0;         Queue Q = new LinkedList();         Q.add(emp.get(id)); // push the 'root' of the sub-tree into the queue         int r = 0;         while (!Q.isEmpty()) {             Employee p = Q.peek();             Q.poll();             r += p.importance;             for (int x: p.subordinates) {   // expand the child nodes                             if (emp.containsKey(x)) {                     Q.add(emp.get(x));                 }             }         }         return r;     } }```
```/*
// Employee info
class Employee {
// It's the unique id of each node;
// unique id of this employee
public int id;
// the importance value of this employee
public int importance;
// the id of direct subordinates
public List subordinates;
};
*/
class Solution {
public int getImportance(List employees, int id) {
Map emp = new HashMap();
for (Employee e: employees) {
emp.put(e.id, e);
}
if (!emp.containsKey(id)) return 0;
Q.add(emp.get(id)); // push the 'root' of the sub-tree into the queue
int r = 0;
while (!Q.isEmpty()) {
Employee p = Q.peek();
Q.poll();
r += p.importance;
for (int x: p.subordinates) {   // expand the child nodes
if (emp.containsKey(x)) {
}
}
}
return r;
}
}```

The idea is the same in Java but there are quite a few syntax difference. Surprisingly, the Java solutions are running slightly faster than the C++ equivalences on the online judge server.

GD Star Rating