Adjacency List + BFS | C# | Simple to understand
Intuition & Approach\n Describe your first thoughts on how to solve this problem. \nFrom the given tree, form a bi-directional graph (adjacency list) and starti
# Intuition & Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\nFrom the given tree, form a bi-directional graph (adjacency list) and starting from the target node, apply BFS traversal, to find all nodes at the distance \'k\'.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N) - as we need to visit all nodes once, both during forming adjacency list and during BFS\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N) - as use a dictionary to form adjaceny list\n***generally this will be O(n * n) since it\'ll be like matrix, but here, every node will have at most 3 connections (left, right, parent)\nHence it\'ll be O(3 * N) => O(N)***\n\n---\n\n\n\n## Please upvote if you like the simplicity of the approach\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     public int val;\n *     public TreeNode left;\n *     public TreeNode right;\n *     public TreeNode(int x) { val = x; }\n * }\n */\npublic class Solution {\n    public IList<int> DistanceK(TreeNode root, TreeNode target, int k) {\n        //if k = 0, we simply return the target node itself\n        if (k == 0)\n            return new List<int>() { target.val };\n\n        //Form a Adjacency List and convert the given tree to graph\n        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();\n        graph.Add(root.val, new List<int>());\n        TreeToGraph(root, graph);\n\n        //Traverse in BFS fashion, starting from the target node, and find all nodes which has distance of k from the target.\n        return BFS(graph, target.val, k);\n    }\n\n    //BFS traversal starting from the target to find nodes at distance K\n    private IList<int> BFS(Dictionary<int, List<int>> graph, int first, int k)\n    {\n        IList<int> result = new List<int>();\n        Queue<int> q = new Queue<int>();\n        HashSet<int> visited = new HashSet<int>();\n        q.Enqueue(first);\n        visited.Add(first);\n        while (k > 0 && q.Count > 0)\n        {\n            int count = q.Count;\n            while (count > 0)\n            {\n                count--;\n                int item = q.Dequeue();\n                for (int i = 0; i < graph[item].Count; i++)\n                {\n                    if (!visited.Contains(graph[item][i]))\n                    {\n                        q.Enqueue(graph[item][i]);\n                        visited.Add(graph[item][i]);\n                    }\n                }\n            }\n            k--;\n        }\n\n        return q.ToList();\n    }\n\n    //Convert tree to graph and for the adjacency list\n    private void TreeToGraph(TreeNode node, Dictionary<int, List<int>> graph)\n    {\n        if (node == null || (node.left == null && node.right == null))\n            return;\n\n        if (node.left != null)\n        {\n            graph[node.val].Add(node.left.val);\n\n            graph.Add(node.left.val, new List<int>());\n            graph[node.left.val].Add(node.val);\n        }\n\n        if (node.right != null)\n        {\n            graph[node.val].Add(node.right.val);\n            \n            graph.Add(node.right.val, new List<int>());\n            graph[node.right.val].Add(node.val);\n        }\n\n        TreeToGraph(node.left, graph);\n        TreeToGraph(node.right, graph);\n    }\n}\n```\n\n---\n\n\n\n## Please upvote if you like the simplicity of the approach\n![Upvote please - effort.jpg](https://assets.leetcode.com/users/images/f11da9aa-9450-4479-9343-bc66f5955a2b_1689046304.0132396.jpeg)\n
['Tree', 'Breadth-First Search', 'Binary Tree', 'C#']