Problem statement

https://binarysearch.com/problems/Binary-Tree-Nodes-Around-Radius/

Solution

Create tree as defaultdict, then use dfs2.

Complexity

It is O(n log n) for time, because of sort and O(n) for space.

Code

class Solution:
    def solve(self, root, target, radius):
        G = defaultdict(list)
        def dfs(node, par):
            if par != None:
                G[node.val] += [par.val]
                G[par.val] += [node.val]
            if node.left: dfs(node.left, node)
            if node.right: dfs(node.right, node)

        V, self.ans = set(), []
        def dfs2(node, d):
            if d == radius: self.ans += [node]
            V.add(node)
            for child in G[node]: 
                if child in V: continue
                dfs2(child, d + 1)

        dfs(root, None)
        dfs2(target, 0)
        return sorted(self.ans)