1. Depth First Search

Intuition

When we kill a process, all its descendants must also be killed. This is naturally a tree traversal problem. The brute force approach scans through all processes for each recursive call to find children of the current process. While this works, it repeatedly searches the entire list, making it inefficient for large inputs.

Algorithm

1. Start with the process to kill and add it to the result list.
2. Scan through the ppid array to find all children of the current process.
3. For each child found, recursively call the function to kill that process and its descendants.
4. Return the accumulated list of all killed processes.

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        if kill == 0:
            return []

        result = [kill]
        for i in range(len(ppid)):
            if ppid[i] == kill:
                result.extend(self.killProcess(pid, ppid, pid[i]))

        return result

Time & Space Complexity

• Time complexity: $O(n^2)$
• Space complexity: $O(n)$

Where $n$ is the length of the pid and ppid.

---

2. Tree Simulation

Intuition

Instead of repeatedly scanning arrays, we can build an actual tree structure upfront. By creating node objects with parent-child relationships, we transform the implicit tree (represented by parallel arrays) into an explicit one. Once built, collecting all descendants becomes a simple tree traversal.

Algorithm

1. Create a Node object for each process ID and store them in a hash map.
2. Iterate through the ppid array to establish parent-child relationships.
3. Starting from the node to kill, perform a DFS to collect all descendant nodes.
4. Add each visited node's value to the result list.

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        mp = {}
        for id in pid:
            mp[id] = Node(id)

        for i in range(len(ppid)):
            if ppid[i] > 0:
                mp[ppid[i]].children.append(mp[pid[i]])

        result = [kill]
        self.getAllChildren(mp[kill], result)
        return result

    def getAllChildren(self, node, result):
        for child in node.children:
            result.append(child.val)
            self.getAllChildren(child, result)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the length of the pid and ppid.

---

3. HashMap + Depth First Search

Intuition

We can simplify the tree simulation by using a hash map that directly maps each parent to its list of children. This avoids creating node objects while still giving us O(1) access to any process's children. The DFS traversal then becomes straightforward.

Algorithm

1. Build a hash map where each key is a parent process ID and the value is a list of its child process IDs.
2. Start with the kill process and add it to the result.
3. Look up the children of the current process in the hash map.
4. For each child, recursively add it and all its descendants to the result.

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        map_dict = {}
        for i in range(len(ppid)):
            if ppid[i] > 0:
                if ppid[i] not in map_dict:
                    map_dict[ppid[i]] = []
                map_dict[ppid[i]].append(pid[i])
        
        result = [kill]
        self.getAllChildren(map_dict, result, kill)
        return result
    
    def getAllChildren(self, map_dict, result, kill):
        if kill in map_dict:
            for child_id in map_dict[kill]:
                result.append(child_id)
                self.getAllChildren(map_dict, result, child_id)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the length of the pid and ppid.

---

4. HashMap + Breadth First Search

Intuition

BFS offers an alternative to DFS for traversing the process tree. Instead of going deep into one branch before backtracking, BFS processes all children at the current level before moving to the next. Both approaches yield the same result but BFS can be more intuitive when thinking about the spread of the kill signal.

Algorithm

1. Build a hash map mapping each parent process ID to its children.
2. Initialize a queue with the kill process.
3. While the queue is not empty:
   • Dequeue a process and add it to the result.
   • Enqueue all of its children.
4. Return the result containing all killed processes.

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        map_dict = {}
        for i in range(len(ppid)):
            if ppid[i] > 0:
                if ppid[i] not in map_dict:
                    map_dict[ppid[i]] = []
                map_dict[ppid[i]].append(pid[i])
        
        queue = deque([kill])
        result = []
        while queue:
            r = queue.popleft()
            result.append(r)
            if r in map_dict:
                for child_id in map_dict[r]:
                    queue.append(child_id)
        
        return result

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the length of the pid and ppid.

---

Common Pitfalls

Forgetting to Include the Kill Process Itself

A common mistake is only collecting the children of the process to kill, but forgetting to include the kill process itself in the result. The killed process must be added to the result list before traversing its descendants.

Not Handling Processes With No Children

When building the parent-to-children map, some processes may have no children (leaf processes). Failing to check if a key exists in the map before accessing its children can cause null pointer exceptions or key errors. Always verify the map contains the key before iterating over children.

Using Linear Search for Each Recursive Call

The brute force approach scans the entire ppid array for each recursive call, leading to O(n^2) complexity. This becomes a problem for large inputs. Building a hash map upfront to store parent-child relationships reduces this to O(n) by providing O(1) child lookups.