# Kill Process — Day 77(Python)

Today’s question is from Leetcode’s daily coding challenge February edition. It is a medium-tagged question on Leetcode. Let us look into the problem statement.

**582****. Kill Process**

Given **n** processes, each process has a unique **PID (process id)** and its **PPID (parent process id)**.

Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.

We use two lists of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.

Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.

**Example 1:**

**Input:**

pid = [1, 3, 10, 5]

ppid = [3, 0, 5, 3]

kill = 5

**Output:** [5,10]

**Explanation:**

3

/ \

1 5

/

10

Kill 5 will also kill 10.

**Note:**

- The given kill id is guaranteed to be one of the given PIDs.
- n >= 1.

One way to start solving this problem is to use a data structure that keeps track of children nodes of all the nodes. We can use a dictionary to store the parent-child relation.

Let us see how we can store that relation.

`parent_dictionary = collections.defaultdict(list)`

for p in range(len(ppid)):

parent_dictionary[ppid[p]].append(pid[p])

Next, we need to identify all the nodes that have to be killed. We start with the input node. We look at who are the children of this node. We then look for children of these children. Keep looking for the children until we reach the leaf nodes. Looks like we need to use BFS or DFS to solve this problem.

We will be solving this problem using BFS.

We need a queue that will keep track of which process needs to be killed. We will take the first node from the queue, look for its children in the dictionary, and add children in the queue. Keep repeating the steps until the queue is empty. Every time we remove the node from the queue add it to the output list.

`import collections`

class ProcessKiller:

def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:

parent_dictionary = collections.defaultdict(list)

output = []

next_process_to_kill = [kill]

for p in range(len(ppid)):

parent_dictionary[ppid[p]].append(pid[p])

while(next_process_to_kill):

kill_proc = next_process_to_kill.pop(0)

output.append(kill_proc)

for process in parent_dictionary[kill_proc]:

next_process_to_kill.append(process)

return output

**Complexity analysis.**

**Time Complexity**

We are visiting each node in ppid and pid to create the dictionary. The time to kill process will take O(N) if we have to kill off the root node. Hence the time complexity is O(N).

**Space Complexity.**

Since we are using a dictionary to store the nodes, the space complexity is O(N), where N is the number of nodes.

We can use DFS to solve this problem too. Since we have solved quite a few problems using DFS, we can directly look into the code snippet.

`import collections`

class ProcessKiller:

def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:

parent_dictionary = collections.defaultdict(list)

output = []

next_process_to_kill = [kill]

for p in range(len(ppid)):

parent_dictionary[ppid[p]].append(pid[p])

def dfs(node):

output.append(node)

for child in parent_dictionary[node]:

dfs(child)

dfs(kill)

return output

**Complexity analysis.**

**Time Complexity**

We are visiting each node in ppid and pid to create the dictionary. The time to kill process will take O(N) if we have to kill off the root node. Hence the time complexity is O(N).

**Space Complexity.**

Since we are using a dictionary to store the nodes, the space complexity is O(N), where N is the number of nodes.