Given a binary tree, a target node in the binary tree, and an integer value k, find all the nodes that are at distance k from the given target node. No parent pointers are available.
Note: You have to return list in sorted order.
Example 1:
Input:      
          20
        /    \
      8       22 
    /   \
   4    12 
       /   \
      10    14
Target Node = 8
K = 2
Output: 10 14 22
Explanation: The three nodes at distance 2
from node 8 are 10, 14, 22.
Example 2:
Input:      
         20
       /    \
      7      24
    /   \
   4     3
        /  
       1    
Target Node = 7
K = 2
Output: 1 24
Your Task:  
You don't need to read input or print anything. Complete the function KDistanceNodes() which takes the root of the tree, target, and K as input parameters and returns a list of nodes at k distance from target in a sorted order.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(Height of tree)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ data of node ≤ 10^{4}
1 ≤ target ≤ 10^{4}
1 ≤ k ≤ 20

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

# Tree Node

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''



class Solution:

    

    def KDistanceNodes(self,root,target,k):

        # code here

        # return the sorted list all nodes at k distance from target

Solutions:
class Solution:

	def childnodes(self, root, k, res):
		if root is None:
			return
		if k == 0:
			res.append(root.data)
			return
		self.childnodes(root.left, k - 1, res)
		self.childnodes(root.right, k - 1, res)

	def findnodes(self, root, k, target, res):
		if root is None:
			return 0
		if root.data == target:
			self.childnodes(root, k, res)
			return 1
		fromleft = self.findnodes(root.left, k, target, res)
		fromright = self.findnodes(root.right, k, target, res)
		if fromleft > 0:
			if k - fromleft == 0:
				res.append(root.data)
			self.childnodes(root.right, k - fromleft - 1, res)
			return fromleft + 1
		if fromright > 0:
			if k - fromright == 0:
				res.append(root.data)
			self.childnodes(root.left, k - fromright - 1, res)
			return fromright + 1
		return 0

	def KDistanceNodes(self, root, target, k):
		res = []
		self.findnodes(root, k, target, res)
		res.sort()
		return res


class Solution:

	def find(self, root, target):
		if root.data == target:
			self.t = root
			return root
		if root.left:
			self.find(root.left, target)
		if root.right:
			self.find(root.right, target)

	def KDistanceNodes(self, root, target, k):
		self.t = 0
		q = deque([root])
		d = {}
		while q:
			node = q.popleft()
			if node.left:
				q.append(node.left)
				d[node.left] = node
			if node.right:
				q.append(node.right)
				d[node.right] = node
		self.find(root, target)
		q.append(self.t)
		distance = 0
		visited = set()
		visited.add(self.t)
		while q:
			n = len(q)
			for i in range(n):
				node = q.popleft()
				if node in d and d[node] not in visited:
					q.append(d[node])
					visited.add(d[node])
				if node.left and node.left not in visited:
					q.append(node.left)
					visited.add(node.left)
				if node.right and node.right not in visited:
					q.append(node.right)
					visited.add(node.right)
			distance += 1
			if distance == k:
				break
		ans = []
		while q:
			node = q.popleft()
			ans.append(node.data)
		return sorted(ans)


class Solution:

	def KDistanceNodes(self, root, target, k):

		def parentTrack(root, parent_track, target):
			queue = []
			parent_track[root] = None
			queue.append(root)
			while queue:
				node = queue[0]
				queue.pop(0)
				if node.left:
					parent_track[node.left] = node
					queue.append(node.left)
				if node.right:
					parent_track[node.right] = node
					queue.append(node.right)
				if node.data == target:
					tar = node
			return tar

		def KDN(root, target, k):
			parent_track = {}
			tar = parentTrack(root, parent_track, target)
			visited = {}
			queue = []
			queue.append(tar)
			visited[tar] = True
			curr_level = 0
			while queue:
				if curr_level == k:
					break
				curr_level += 1
				for i in range(len(queue)):
					node = queue[0]
					queue.pop(0)
					if node.left and node.left not in visited:
						queue.append(node.left)
						visited[node.left] = True
					if node.right and node.right not in visited:
						queue.append(node.right)
						visited[node.right] = True
					if parent_track[node] and parent_track[node] not in visited:
						queue.append(parent_track[node])
						visited[parent_track[node]] = True
			result = []
			for i in range(len(queue)):
				result.append(queue[i].data)
			result.sort()
			return result
		return KDN(root, target, k)


class Solution:
	pathfound = 0
	ans = []

	def gen(self, root, dist, k, visited):
		if root == None:
			return
		if dist == k:
			self.ans.append(root.data)
			return
		if root.left != None and root.left.data not in visited:
			visited[root.left.data] = 1
			self.gen(root.left, dist + 1, k, visited)
		if root.right != None and root.right.data not in visited:
			visited[root.right.data] = 1
			self.gen(root.right, dist + 1, k, visited)

	def pathgen(self, root, target, path, pathele):
		if root == None:
			return
		if root.data == target:
			path.append(root)
			pathele.append(root.data)
			self.pathfound = 1
			return
		if root.left != None and self.pathfound == 0:
			path.append(root)
			pathele.append(root.data)
			self.pathgen(root.left, target, path, pathele)
			if self.pathfound == 0:
				path.pop()
				pathele.pop()
		if root.right != None and self.pathfound == 0:
			path.append(root)
			pathele.append(root.data)
			self.pathgen(root.right, target, path, pathele)
			if self.pathfound == 0:
				path.pop()
				pathele.pop()

	def KDistanceNodes(self, root, target, k):
		self.pathfound = 0
		self.ans = []
		path = []
		pathele = []
		self.pathgen(root, target, path, pathele)
		visited = dict()
		for i in pathele:
			visited[i] = 1
		dist = 0
		while len(path) != 0:
			node = path.pop()
			self.gen(node, dist, k, visited)
			dist += 1
		return sorted(self.ans)


from queue import Queue

class Solution:

	def KDistanceNodes(self, root, target, k):
		parentchild = dict()
		hittTarget = None

		def adding(root, parentchild, target):
			nonlocal hittTarget
			if root.data == target:
				hittTarget = root
			if root.left != None:
				parentchild[root.left.data] = root
				adding(root.left, parentchild, target)
			if root.right != None:
				parentchild[root.right.data] = root
				adding(root.right, parentchild, target)
			return
		adding(root, parentchild, target)
		visited = dict()

		def logic(root, k):
			nonlocal visited
			q = Queue()
			q.put(hittTarget)
			visited[hittTarget.data] = True
			while q.empty() == False and k != 0:
				times = q.qsize()
				for i in range(times):
					root = q.get()
					if root.left != None and visited.get(root.left.data) == None:
						q.put(root.left)
						visited[root.left.data] = True
					if root.right != None and visited.get(root.right.data) == None:
						q.put(root.right)
						visited[root.right.data] = True
				if parentchild.get(root.data) != None and visited.get(parentchild.get(root.data).data) == None:
					this = parentchild.get(root.data)
					q.put(this)
					visited[this.data] = True
				k -= 1
			mylist = list()
			while q.empty() == False:
				this = q.get()
				if this != None:
					mylist.append(this.data)
			return mylist
		mylist = logic(root, k)
		mylist.sort()
		return mylist


class Solution:

	def findDown(self, root, k, ans):
		if root == None:
			return
		if k == 0:
			ans.append(root.data)
			return
		self.findDown(root.left, k - 1, ans)
		self.findDown(root.right, k - 1, ans)

	def Find(self, root, target, k, ans):
		if root == None:
			return -1
		if root.data == target:
			self.findDown(root, k, ans)
			return 0
		left = self.Find(root.left, target, k, ans)
		if left != -1:
			if left + 1 == k:
				ans.append(root.data)
			else:
				self.findDown(root.right, k - (left + 2), ans)
			return left + 1
		right = self.Find(root.right, target, k, ans)
		if right != -1:
			if right + 1 == k:
				ans.append(root.data)
			else:
				self.findDown(root.left, k - (right + 2), ans)
			return right + 1
		return -1

	def KDistanceNodes(self, root, target, k):
		ans = []
		self.Find(root, target, k, ans)
		ans.sort()
		return ans


class Solution:

	def findNode(self, root, target):
		if root == None:
			return None
		if root.data == target:
			return root
		l = self.findNode(root.left, target)
		r = self.findNode(root.right, target)
		if l != None:
			return l
		else:
			return r

	def KDistanceNodes(self, root, target, k):
		ans = []
		target = self.findNode(root, target)
		parentDic = {}
		q = [root]
		while len(q) > 0:
			p = q[0]
			q.pop(0)
			if p.left != None:
				parentDic[p.left] = p
				q.append(p.left)
			if p.right != None:
				parentDic[p.right] = p
				q.append(p.right)
		visitedDic = {target: 1}
		q = [target]
		while len(q) > 0:
			l = len(q)
			k -= 1
			if k < 0:
				break
			for _ in range(l):
				node = q[0]
				q.pop(0)
				if node.left != None and visitedDic.get(node.left) == None:
					visitedDic[node.left] = 1
					if k == 0:
						ans.append(node.left.data)
					q.append(node.left)
				if node.right != None and visitedDic.get(node.right) == None:
					visitedDic[node.right] = 1
					if k == 0:
						ans.append(node.right.data)
					q.append(node.right)
				if parentDic.get(node) != None and visitedDic.get(parentDic[node]) == None:
					visitedDic[parentDic[node]] = 1
					if k == 0:
						ans.append(parentDic[node].data)
					q.append(parentDic[node])
		return sorted(ans)


class Solution:

	def findTarget(self, root, target, nodes):
		if root is None:
			return False
		if root.data == target:
			nodes.append(root)
			return True
		if self.findTarget(root.right, target, nodes):
			nodes.append(root)
			return True
		elif self.findTarget(root.left, target, nodes):
			nodes.append(root)
			return True
		return False

	def KDistanceNodes(self, root, target, k):
		nodes = []
		self.findTarget(root, target, nodes)
		ans = self.findKChild(nodes[0], k)
		for i in range(1, len(nodes)):
			node = nodes[i]
			if i == k:
				ans.append(node.data)
				break
			if node.right == nodes[i - 1]:
				ans += self.findKChild(node.left, k - i - 1)
			else:
				ans += self.findKChild(node.right, k - i - 1)
		ans.sort()
		return ans

	def findKChild(self, root, k):
		if root is None:
			return []
		if k == 0:
			return [root.data]
		return self.findKChild(root.left, k - 1) + self.findKChild(root.right, k - 1)


class Solution:

	def KDistanceNodes(self, root, target, k):
		lista = []
		lista = self.findTarget(root, target, lista)
		lista_final = []
		lista_final = self.findKChild(lista[0], k)
		for i in range(1, len(lista)):
			node = lista[i]
			if i == k:
				lista_final.append(node.data)
			if node.right == lista[i - 1]:
				lista_final += self.findKChild(node.left, k - i - 1)
			else:
				lista_final += self.findKChild(node.right, k - i - 1)
		lista_final.sort()
		return lista_final

	def findTarget(self, root, target, lista):
		if root is None:
			return lista
		if root.data == target:
			lista.append(root)
			return lista
		if self.findTarget(root.right, target, lista):
			lista.append(root)
			return lista
		elif self.findTarget(root.left, target, lista):
			lista.append(root)
			return lista
		return lista

	def findKChild(self, root, k):
		if root is None or k < 0:
			return []
		if k == 0:
			return [root.data]
		left_subtree = self.findKChild(root.left, k - 1)
		right_subtree = self.findKChild(root.right, k - 1)
		return left_subtree + right_subtree


class Solution:

	def find_target(self, root, target, nodes):
		if root is None:
			return False
		if root.data == target:
			nodes.append(root)
			return True
		if self.find_target(root.right, target, nodes):
			nodes.append(root)
			return True
		elif self.find_target(root.left, target, nodes):
			nodes.append(root)
			return True
		return False

	def findKchild(self, root, k):
		if root is None:
			return []
		if k == 0:
			return [root.data]
		return self.findKchild(root.left, k - 1) + self.findKchild(root.right, k - 1)

	def KDistanceNodes(self, root, target, k):
		nodes = []
		self.find_target(root, target, nodes)
		temp = self.findKchild(nodes[0], k)
		for i in range(1, len(nodes)):
			node = nodes[i]
			if i == k:
				temp.append(node.data)
				break
			if node.right == nodes[i - 1]:
				temp += self.findKchild(node.left, k - i - 1)
			else:
				temp += self.findKchild(node.right, k - i - 1)
		temp.sort()
		return temp


class Solution:
	targetnode = None

	def findTarget(self, root, target):
		if root == None:
			return
		if root.data == target:
			self.targetnode = root
			return
		self.findTarget(root.left, target)
		self.findTarget(root.right, target)

	def makeParent(self, root, parent):
		q = deque()
		q.append(root)
		while q:
			cur = q.popleft()
			if cur.left:
				parent[cur.left] = cur
				q.append(cur.left)
			if cur.right:
				parent[cur.right] = cur
				q.append(cur.right)

	def KDistanceNodes(self, root, target, k):
		self.findTarget(root, target)
		target = self.targetnode
		parent = {}
		self.makeParent(root, parent)
		visited = {target}
		q = deque()
		q.append(target)
		level = 0
		while q:
			size = len(q)
			if level == k:
				break
			level += 1
			for i in range(size):
				cur = q.popleft()
				if cur.left and cur.left not in visited:
					q.append(cur.left)
					visited.add(cur.left)
				if cur.right and cur.right not in visited:
					q.append(cur.right)
					visited.add(cur.right)
				if parent.get(cur) and parent.get(cur) not in visited:
					q.append(parent.get(cur))
					visited.add(parent.get(cur))
		ans = []
		while q:
			node = q.popleft()
			ans.append(node.data)
		return sorted(ans)


from collections import deque

class Solution:

	def KDistanceNodes(self, root, target, k):
		q = deque([root])
		dic = {}
		while q:
			n = len(q)
			for i in range(n):
				node = q.popleft()
				if node.data == target:
					Target = node
				if node.left:
					q.append(node.left)
					dic[node.left] = node
				if node.right:
					q.append(node.right)
					dic[node.right] = node
		c = 0
		vis = []
		ans = [Target]
		while c < k:
			for i in range(len(ans)):
				tar = ans.pop(0)
				vis.append(tar)
				if tar.left and tar.left not in vis:
					ans.append(tar.left)
					vis.append(tar.left)
				if tar.right and tar.right not in vis:
					ans.append(tar.right)
					vis.append(tar.right)
				if dic.get(tar) != None and dic[tar] not in vis:
					ans.append(dic[tar])
					vis.append(dic[tar])
			c += 1
		final = []
		while ans:
			final.append(ans.pop(0).data)
		final.sort()
		return final


class Solution:

	def KDistanceNodes(self, root, target, k):
		path = []
		self.find_path(root, target, 0, path)
		nodes = []
		n = len(path)
		for i in range(n):
			path[i]['depth'] = path[n - 1]['depth'] - path[i]['depth']
		for i in range(n - 1):
			if k == path[i]['depth']:
				nodes.append(path[i]['node'].data)
			if path[i]['node'].left != None and path[i]['node'].left.data == path[i + 1]['node'].data:
				temp = []
				self.nodesAtDepth(path[i]['node'].right, k - path[i]['depth'] - 1, temp)
				for x in temp:
					nodes.append(x)
			elif path[i]['node'].right != None and path[i]['node'].right.data == path[i + 1]['node'].data:
				temp = []
				self.nodesAtDepth(path[i]['node'].left, k - path[i]['depth'] - 1, temp)
				for x in temp:
					nodes.append(x)
		temp = []
		self.nodesAtDepth(path[n - 1]['node'], k - path[n - 1]['depth'], temp)
		for x in temp:
			nodes.append(x)
		return sorted(nodes)

	def find_path(self, root, target, depth, path):
		if root == None:
			return False
		path.append({'node': root, 'depth': depth})
		if root.data == target:
			return True
		if self.find_path(root.left, target, depth + 1, path) or self.find_path(root.right, target, depth + 1, path):
			return True
		path.pop(-1)
		return False

	def nodesAtDepth(self, root, depth, arr):
		if root == None:
			return
		if depth == 0:
			arr.append(root.data)
			return
		self.nodesAtDepth(root.left, depth - 1, arr)
		self.nodesAtDepth(root.right, depth - 1, arr)


from collections import defaultdict

class Solution:

	def KDistanceNodes(self, root, target, k):
		gr = defaultdict(list)

		def makeGraph(root, prev):
			if not root:
				return
			if prev:
				gr[root.data].append(prev)
			if root.left:
				gr[root.data].append(root.left.data)
			if root.right:
				gr[root.data].append(root.right.data)
			makeGraph(root.left, root.data)
			makeGraph(root.right, root.data)
		makeGraph(root, None)
		res = [target]
		visited = set(res)
		for i in range(k):
			new_result = []
			for parent_node in res:
				for child_node in gr[parent_node]:
					if child_node not in visited:
						new_result.append(child_node)
			res = new_result
			visited |= set(res)
		return sorted(res)