# LeetCode 582: Kill Process

## Problem Restatement

We are given a list of process IDs and their parent process IDs.

Each process forms part of a process tree.

If a process is killed, then all of its child processes are also killed recursively.

Given a process ID called `kill`, return all process IDs that will be terminated.

The result may be returned in any order. The official problem defines:

```text
pid[i]  = process ID
ppid[i] = parent process ID of pid[i]
```

and guarantees that exactly one process has parent `0`, which is the root process. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0500-0599/0582.Kill%20Process/README_EN.md?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| `pid` | List of process IDs |
| `ppid` | Parent process IDs |
| `kill` | Process to terminate |
| Output | All processes that will be killed |

Constraints:

| Constraint | Value |
|---|---|
| `1 <= pid.length <= 5 * 10^4` | Number of processes |
| `pid.length == ppid.length` | Arrays have equal size |
| Process IDs are unique | No duplicate process IDs |

## Examples

Example 1:

```python
pid = [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
```

The process tree is:

```text
3
├── 1
└── 5
    └── 10
```

If we kill process `5`, then process `10` is also terminated.

Output:

```python
[5, 10]
```

Example 2:

```python
pid = [1]
ppid = [0]
kill = 1
```

Output:

```python
[1]
```

There is only one process.

## First Thought: Scan Repeatedly

One idea is:

1. Start with the `kill` process.
2. Scan all processes.
3. If a process has a killed parent, mark it as killed.
4. Repeat until no new process is added.

This works, but repeated scanning is inefficient.

If there are many processes, we may scan the full list many times.

## Key Insight

The process structure is a tree.

Each process points to its parent:

```text
child -> parent
```

But for traversal, we want the reverse direction:

```text
parent -> list of children
```

So we first build an adjacency list.

For example:

```python
pid  = [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
```

becomes:

```python
{
    3: [1, 5],
    5: [10]
}
```

Then starting from `kill`, we perform DFS or BFS to visit all descendants.

Every visited node is a killed process.

## Algorithm

1. Build a hash map:

```python
parent -> children
```

2. For every process:
   - Add `pid[i]` to the child list of `ppid[i]`.

3. Start DFS or BFS from `kill`.

4. Add each visited process to the result.

5. Visit all children recursively.

6. Return the collected processes.

## Correctness

The adjacency list stores exactly the children of every process.

The traversal starts from the process `kill`. Therefore, the killed process itself is always included in the result.

Whenever the traversal visits a process, it recursively visits all of its children from the adjacency list. Since every child process is directly connected to its parent, every descendant of `kill` is eventually reached.

Processes outside the subtree of `kill` are never visited because there is no traversal path from `kill` to those nodes.

Thus, the traversal visits exactly the processes that must be terminated.

## Complexity

Let:

```text
n = number of processes
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Build graph once and visit each process at most once |
| Space | `O(n)` | Store adjacency list and recursion/queue |

## Implementation

```python
from collections import defaultdict

class Solution:
    def killProcess(
        self,
        pid: list[int],
        ppid: list[int],
        kill: int,
    ) -> list[int]:
        children = defaultdict(list)

        for child, parent in zip(pid, ppid):
            children[parent].append(child)

        result = []

        def dfs(process: int) -> None:
            result.append(process)

            for child in children[process]:
                dfs(child)

        dfs(kill)

        return result
```

## Code Explanation

This creates the adjacency list:

```python
children = defaultdict(list)
```

Each key is a parent process.

Each value is the list of child processes.

This loop builds the graph:

```python
for child, parent in zip(pid, ppid):
    children[parent].append(child)
```

For example:

```python
parent = 3
child = 5
```

creates:

```python
children[3] = [5]
```

The DFS function visits one process:

```python
def dfs(process):
```

First we record the process:

```python
result.append(process)
```

Then recursively visit all children:

```python
for child in children[process]:
    dfs(child)
```

Finally:

```python
dfs(kill)
```

starts the traversal from the process that must be terminated.

## BFS Alternative

A breadth-first solution also works.

```python
from collections import defaultdict, deque

class Solution:
    def killProcess(
        self,
        pid: list[int],
        ppid: list[int],
        kill: int,
    ) -> list[int]:
        children = defaultdict(list)

        for child, parent in zip(pid, ppid):
            children[parent].append(child)

        queue = deque([kill])
        result = []

        while queue:
            process = queue.popleft()
            result.append(process)

            for child in children[process]:
                queue.append(child)

        return result
```

DFS and BFS both visit exactly the same subtree.

## Testing

```python
def run_tests():
    s = Solution()

    assert sorted(
        s.killProcess(
            [1, 3, 10, 5],
            [3, 0, 5, 3],
            5,
        )
    ) == [5, 10]

    assert sorted(
        s.killProcess(
            [1],
            [0],
            1,
        )
    ) == [1]

    assert sorted(
        s.killProcess(
            [1, 2, 3, 4, 5],
            [0, 1, 1, 2, 2],
            2,
        )
    ) == [2, 4, 5]

    assert sorted(
        s.killProcess(
            [1, 2, 3],
            [0, 1, 2],
            1,
        )
    ) == [1, 2, 3]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Sample tree | Basic recursive kill |
| Single process | Minimum case |
| Process with multiple children | Checks branching |
| Deep chain | Checks recursive descendant traversal |
| Killing leaf node | Should return only that process |