Teaching Kids Programming – Remove a Node and Subtree using Depth First Search or Breadth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Remove a node (and nodes belong to that subtree) from a Tree is the same as The Process Killing Algorithms using Depth First Search or Breadth First Search (Kill a 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 list 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.

Remove a Node and Subtree using Bruteforce Algorithm

For each node to kill/remove, we can go through the array to find out the nodes whose parent is that and recursively remove it. For each node to take out, we need O(N) time to find out the nodes whose parent is that and there are N nodes thus overall time complexity is O(N^2).

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        if kill == 0:
            return []
        ans = [kill]
        for i in range(len(ppid)):
            if ppid[i] == kill:
                ans += self.killProcess(pid, ppid, pid[i])
        return ans     

We spend time to find out the children nodes for a parent – which can be pre-processed and stored in a hash table where the keys are the parents, and values are the list of the children nodes.

Remove a Node and Subtree using Depth First Search Algorithm

We know a node and its parent, sure we can process to have a parent to kids relations where the keys are parents, and values are list of children nodes. And then we can easily perform Depth First Search Algorithm to find out all the nodes in the descendent. We can also construct a Tree class but the idea is the same.

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:       
        parent = defaultdict(list)
        for n, p in zip(pid, ppid):
            parent[p].append(n)
            
        def dfs(root):
            ans = [root]
            for c in parent[root]:
                ans += dfs(c)
            return ans

        return dfs(kill)

Time and space complexity is O(N) – as we need at most traverse each node in the tree twice.

Remove a Node and Subtree using Breadth First Search Algorithm

Breadth First Search Algorithm (BFS) is a level-by-level traversal algorithm for the Trees and Graphs. We use a queue (double-ended queue, First In First Out) to store the nodes of the same level.

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        parent = defaultdict(list)
        for n, p in zip(pid, ppid):
            parent[p].append(n)
        ans = []
        q = deque([kill])        
        while q:
            x = len(q)
            for _ in range(x):
                cur = q.popleft()
                ans.append(cur)
                for n in parent[cur]:
                    q.append(n)
        return ans

Same time and space complexity O(N).

–EOF (The Ultimate Computing & Technology Blog) —