Skip to content

General Tree Top-Down DFS

Table of Contents

1376. Time Needed to Inform All Employees

1376. Time Needed to Inform All Employees - Python Solution
from collections import defaultdict, deque
from typing import List


# DFS
def numOfMinutesDFS(
    n: int, headID: int, manager: List[int], informTime: List[int]
) -> int:
    graph = defaultdict(list)
    for i in range(n):
        if manager[i] != -1:
            graph[manager[i]].append(i)

    def dfs(node):
        time = 0
        for sub in graph[node]:
            time = max(time, dfs(sub))
        return time + informTime[node]

    return dfs(headID)


# BFS
def numOfMinutesBFS(
    n: int, headID: int, manager: List[int], informTime: List[int]
) -> int:
    graph = defaultdict(list)
    for i in range(n):
        if manager[i] != -1:
            graph[manager[i]].append(i)

    q = deque([(headID, 0)])
    max_time = 0

    while q:
        node, time = q.popleft()
        max_time = max(max_time, time)
        for sub in graph[node]:
            q.append((sub, time + informTime[node]))

    return max_time


n = 6
headID = 2
manager = [2, 2, -1, 2, 2, 2]
informTime = [0, 0, 1, 0, 0, 0]
print(numOfMinutesDFS(n, headID, manager, informTime))  # 1
print(numOfMinutesBFS(n, headID, manager, informTime))  # 1

1443. Minimum Time to Collect All Apples in a Tree

  • LeetCode | LeetCode CH (Medium)

  • Tags: hash table, tree, depth first search, breadth first search

1377. Frog Position After T Seconds

3067. Count Pairs of Connectable Servers in a Weighted Tree Network

3372. Maximize the Number of Target Nodes After Connecting Trees I

3372. Maximize the Number of Target Nodes After Connecting Trees I - Python Solution
from typing import Callable, List, Tuple


def maxTargetNodes(
    edges1: List[List[int]], edges2: List[List[int]], k: int
) -> List[int]:
    n = len(edges1) + 1
    m = len(edges2) + 1

    def calc_tree(
        edges: List[List[int]], k: int
    ) -> Tuple[int, Callable[[int, int, int], int]]:
        g = [[] for _ in range(len(edges) + 1)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        diameter = 0

        def dfs_diameter(x: int, fa: int) -> int:
            nonlocal diameter
            max_len = 0
            for y in g[x]:
                if y != fa:
                    sub_len = dfs_diameter(y, x) + 1
                    diameter = max(diameter, max_len + sub_len)
                    max_len = max(max_len, sub_len)
            return max_len

        dfs_diameter(0, -1)

        def dfs(x: int, fa: int, d: int) -> int:
            if d > k:
                return 0
            cnt = 1
            for y in g[x]:
                if y != fa:
                    cnt += dfs(y, x, d + 1)
            return cnt

        return diameter, dfs

    max2 = 0
    if k:
        diameter, dfs = calc_tree(edges2, k - 1)
        if diameter < k:
            max2 = m  # All nodes in the second tree are target nodes
        else:
            max2 = max(dfs(i, -1, 0) for i in range(m))

    diameter, dfs = calc_tree(edges1, k)
    if diameter <= k:
        return [n + max2] * n  # All nodes in the first tree are target nodes
    return [dfs(i, -1, 0) + max2 for i in range(n)]

2467. Most Profitable Path in a Tree

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, tree, depth first search, breadth first search, graph

3373. Maximize the Number of Target Nodes After Connecting Trees II

1766. Tree of Coprimes

3425. Longest Special Path

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, hash table, tree, depth first search, sliding window

2791. Count Paths That Can Form a Palindrome in a Tree

  • LeetCode | LeetCode CH (Hard)

  • Tags: dynamic programming, bit manipulation, tree, depth first search, bitmask

Comments