Python | Convert Tree into Undirected Graph, Traverse Graph K Levels w/ BFS (Level Order Traversal)
Strategy: \nConvert Tree into Undirected Graph. Traverse graph in level order until the Kth level from the input target node reached.\n\nWhy convert tree into u
# Strategy: \nConvert Tree into Undirected Graph. Traverse graph in level order until the Kth level from the input target node reached.\n\n**Why convert tree into undirected graph?**\nTraversing trees are built around traversing **down** to children. But for this problem, we want to know all neighbors of a node (parent **and** children, not *just* children) so we traverse vertically and horizontally (ex:  `k` = 2 means it should include a parent node 2 levels up and sister nodes 2 level to the right or left as well as children nodes 2 levels down). \n\nAs a result, reconstruct the tree into an undirected graph `{node: [list of neighbor nodes]}` so you can find parent node easily so you can always find every node 1 level away, not just children. Re: [TreeNode only has `left` and `right`, no `parent` field]. You can use DFS or BFS to construct an undirected graph. \n\nTo actually **find** the result nodes that are `k` distance away, level order traverse [BFS!] until the level == k!\n\n**Upvote** if you found this useful!\n\n# Complexity\n- Time complexity:\n$$O(2n)$$ -> $$O(n)$$. We traverse full tree to build graph. Then potentially traverse whole graph when looking for `kth` distant nodes. \n\n- Space complexity:\n$$ O(n) $$. Size of graph and queue. \n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, x):\n#         self.val = x\n#         self.left = None\n#         self.right = None\n\nclass Solution:\n    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:\n        res = []\n        if k == 0:\n            res = [target.val]\n            return res\n        \n        # node: [list of neighbor nodes]\n        graph = collections.defaultdict(list)\n        \n        # construct graph using BFS\n        q = collections.deque([root])\n        \n        while q: \n            for i in range(len(q)):\n                node = q.popleft()\n                \n                if node.left:\n                    # bidirectional \n                    graph[node].append(node.left)\n                    graph[node.left].append(node)\n                    q.append(node.left)\n                \n                if node.right:\n                    # bidirectional \n                    graph[node].append(node.right)\n                    graph[node.right].append(node)\n                    q.append(node.right)\n        \n        # traverse the newly formed graph in level order (BFS)\n        visited = set([target])\n        \n        q = collections.deque([target])\n        level = 0\n        while q:\n            for i in range(len(q)): # traverse everything at this level\n                node = q.popleft()\n                # print("visiting node", node.val)\n                # print("level away from target:", level)\n                if level == k:\n                    res.append(node.val)\n                # only continue to traverse node neighbors if target level not reached. \n                else:\n                    for edge in graph[node]:\n                        if edge not in visited:\n                            visited.add(edge)\n                            q.append(edge)\n            level += 1\n        return res\n```
['Tree', 'Breadth-First Search', 'Graph', 'Python3']