Given a Binary Tree of size N and an integer K. Print all nodes that are at distance k from root (root is considered at distance 0 from itself). Nodes should be printed from left to right. If k is more that height of tree, nothing should be printed.
For example, if below is given tree and k is 2. Output should be 4 5 6.
          1
       /     \
     2        3
   /         /   \
  4        5    6 
     \
      8
Example 1:
Input:
K = 0
      1
    /   \
   3     2
Output: 1
Example 2:
Input:
K = 3
        3
       /
      2
       \
        1
      /  \
     5    3
Output: 5 3
Your Task:
You don't have to take input. Complete the function Kdistance() that accepts root node and k as parameter and return the value of the nodes that are at a distance k from the root. (The values are returned as vector in cpp, as ArrayList in java and list in python)
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= N <= 10^{4}
0 <= K <= 30

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3







'''

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

'''

def KDistance(root,k):

    '''

    :param root: root of given tree.

    :param k: distance k from root

    :return: list of all nodes that are at distance k from root.

    '''

    # code here

Solutions:
def KDistance(root, k):
	q = [root]
	l = 0
	res = []
	while q:
		le = len(q)
		for i in range(le):
			p = q.pop(0)
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
			if l == k:
				res.append(p.data)
		l += 1
	return res if res else []


def KDistance(root, k):
	if k == 0:
		return [root.data]
	q = deque([root])
	ans = []
	d = 0
	while q:
		n = len(q)
		for i in range(n):
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		d += 1
		if d == k:
			break
	while q:
		node = q.popleft()
		ans.append(node.data)
	return ans


def KDistance(root, k):
	queue = deque()
	queue.append(root)
	flag = False
	while queue:
		size = len(queue)
		if k == 0:
			subList = []
			while size:
				popped = queue.popleft()
				subList.append(popped.data)
				size -= 1
			return subList
		while size:
			popped = queue.popleft()
			if popped.left:
				queue.append(popped.left)
			if popped.right:
				queue.append(popped.right)
			size -= 1
		k -= 1
	return []


def KDistance(root, k):
	arr = []
	solve(root, k, arr)
	return arr

def solve(root, k, arr):
	if root == None:
		return
	if k == 0:
		arr.append(root.data)
	solve(root.left, k - 1, arr)
	solve(root.right, k - 1, arr)


def tt(root, k, a, b):
	if not root:
		return
	if a > k:
		return
	if k == a:
		b.append(root.data)
		return
	tt(root.left, k, a + 1, b)
	tt(root.right, k, a + 1, b)
	return

def KDistance(root, k):
	a = 0
	b = []
	tt(root, k, a, b)
	return b


def slove(root, k, m, ans):
	if root == None:
		return
	if m == k:
		ans.append(root.data)
	slove(root.left, k, m + 1, ans)
	slove(root.right, k, m + 1, ans)

def KDistance(root, k):
	ans = []
	slove(root, k, 0, ans)
	return ans


def KDistance(root, k):

	def fun(root, k, l, level):
		if root is None:
			return
		if k == level:
			if root.data:
				l.append(root.data)
			return
		fun(root.left, k, l, level + 1)
		fun(root.right, k, l, level + 1)
		return
	l = []
	level = 0
	fun(root, k, l, level)
	return l


def distance(root, ans, level, k):
	if root == None:
		return
	if level == k:
		ans.append(root.data)
	distance(root.left, ans, level + 1, k)
	distance(root.right, ans, level + 1, k)

def KDistance(root, k):
	ans = []
	distance(root, ans, 0, k)
	return ans


def KDistance(root, k):
	res = []

	def dfs(root, k):
		if not root:
			return
		if k == 0:
			res.append(root.data)
			return
		dfs(root.left, k - 1)
		dfs(root.right, k - 1)
	dfs(root, k)
	return res


def check(root, l, k, x):
	if root is None:
		return
	if l == k:
		x.append(root.data)
	check(root.left, l + 1, k, x)
	check(root.right, l + 1, k, x)

def KDistance(root, k):
	x = []
	check(root, 0, k, x)
	return x


from collections import deque

def KDistance(root, k):
	if root == None:
		return -1
	if k == 0:
		return [root.data]
	dQ = deque()
	dQ.append(root)
	tracker = 0
	while dQ:
		tracker += 1
		times = len(dQ)
		while times:
			holdnode = dQ.popleft()
			if holdnode.left != None:
				dQ.append(holdnode.left)
			if holdnode.right != None:
				dQ.append(holdnode.right)
			times -= 1
		if k == tracker:
			resultlist = list()
			for node in dQ:
				resultlist.append(node.data)
			return resultlist
	return []


def KDistance(root, k):

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


def KDistance(root, k):
	return findEle(root, 0, k, [])

def findEle(root, l, k, res):
	if root == None:
		return res
	if l == k:
		res.append(root.data)
		return res
	findEle(root.left, l + 1, k, res)
	findEle(root.right, l + 1, k, res)
	return res


def KDistance(root, k):
	array = []
	_Kdistance(root, k, array)
	return array

def _Kdistance(node, k, array):
	if node:
		if k == 0:
			array.append(node.data)
		else:
			_Kdistance(node.left, k - 1, array)
			_Kdistance(node.right, k - 1, array)


def travel(root, k, d=[]):
	if root is None:
		return []
	if not k:
		d.append(root.data)
		return None
	travel(root.left, k - 1, d)
	travel(root.right, k - 1, d)

def KDistance(root, k):
	d = []
	travel(root, k, d)
	return d


def fun(root, level, l):
	if root == None:
		return
	if level >= len(l):
		l.append([])
	l[level].append(root.data)
	fun(root.left, level + 1, l)
	fun(root.right, level + 1, l)

def KDistance(root, k):
	l = []
	fun(root, 0, l)
	if k > len(l):
		return []
	else:
		res = l[k]
		return res


def fun(root, level, l, k):
	if root == None:
		return
	if level == k:
		l.append(root.data)
	fun(root.left, level + 1, l, k)
	fun(root.right, level + 1, l, k)

def h(root):
	if root == None:
		return 0
	l = h(root.left)
	r = h(root.right)
	m = max(l, r) + 1
	return m

def KDistance(root, k):
	l = []
	fun(root, 0, l, k)
	t = h(root) - 1
	if k <= t:
		return l
	else:
		return []


def solve(root, k, arr):
	if root is not None:
		if k == 0:
			arr.append(root.data)
		else:
			solve(root.left, k - 1, arr)
			solve(root.right, k - 1, arr)

def KDistance(root, k):
	arr = []
	solve(root, k, arr)
	return arr


def KDistance(root, k):
	ans = []

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


def KDistance(root, k):

	def helper(root, to, l):
		if root == None or to > k:
			return
		if to == k:
			l.append(root.data)
			return
		helper(root.left, to + 1, l)
		helper(root.right, to + 1, l)
	l = []
	helper(root, 0, l)
	return l


def KDistance(root, k):
	ans = []

	def helper(root, k):
		if not root:
			return
		if k == 0:
			ans.append(root.data)
		helper(root.left, k - 1)
		helper(root.right, k - 1)
	helper(root, k)
	return ans


def KDistance(root, k):
	if root == None:
		return True
	queue = deque()
	queue.append(root)
	ans = []
	count = 0
	while queue:
		count += 1
		n = len(queue)
		m = n
		if count == k + 1:
			ans = [x.data for x in queue]
			break
		while n:
			node = queue.popleft()
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
			n = n - 1
	return ans


def solve(root, k, l, ans):
	if root == None:
		return
	if l == k:
		ans.append(root.data)
	l += 1
	solve(root.left, k, l, ans)
	solve(root.right, k, l, ans)

def KDistance(root, k):
	if root == None:
		return
	ans = []
	solve(root, k, 0, ans)
	return ans


def KDistance(root, k):
	from collections import deque
	q = deque()
	if root:
		q.append(root)
	c = 0
	while q:
		size = len(q)
		if c == k:
			break
		for i in range(size):
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		c += 1
	ans = []
	for i in q:
		ans += [i.data]
	return ans


def KDistance(root, k):
	l = [0]
	q = [root]
	m = []
	while q:
		z = q.pop(0)
		lev = l.pop(0)
		if lev == k:
			m.append(z.data)
		if z.left:
			q.append(z.left)
			l.append(lev + 1)
		if z.right:
			q.append(z.right)
			l.append(lev + 1)
	return m


def KDistance(root, k):
	q = []
	q.append(root)
	if k == 0:
		res = [root.data]
		return res
	c = 0
	res = []
	while q:
		n = len(q)
		c += 1
		while n > 0:
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			n -= 1
		if c == k:
			for i in q:
				res.append(i.data)
			break
	return res


def recur(root, ans, level, k):
	if not root:
		return
	if level == k:
		ans.append(root.data)
	recur(root.left, ans, level + 1, k)
	recur(root.right, ans, level + 1, k)

def KDistance(root, k):
	ans = []
	recur(root, ans, 0, k)
	if not len(ans):
		return ans
	return ans


def KDistance(root, k):
	if root == None:
		return []
	if k == 0 and root != None:
		return [root.data]
	lans = KDistance(root.left, k - 1)
	rans = KDistance(root.right, k - 1)
	return lans + rans


def KDistance(root, k):
	l = []

	def di(root, k, l):
		if root == None:
			return
		if k == 0:
			return l.append(root.data)
		else:
			di(root.left, k - 1, l)
			di(root.right, k - 1, l)
	di(root, k, l)
	return l


def KDistance(root, k):
	l = []

	def retk(root, k):
		if root == None:
			return
		if k == 0:
			l.append(root.data)
		retk(root.left, k - 1)
		retk(root.right, k - 1)
	retk(root, k)
	return l


def KDistance(root, k):
	j = 0
	queue = [root]
	while queue:
		level = []
		vals = []
		for i in queue:
			if i == None:
				continue
			vals.append(i.data)
			level.append(i.left)
			level.append(i.right)
		if j == k:
			return vals
		j += 1
		queue = level
	return []


def KDistance(root, k):
	level = 0
	list = []

	def distance(root, level, list):
		if not root:
			return
		if k == level:
			list.append(root.data)
		distance(root.left, level + 1, list)
		distance(root.right, level + 1, list)
	distance(root, level, list)
	return list


def KDistance(root, k):
	q = [root]
	count = 0
	list = []
	while q:
		if k == count:
			for i in q:
				list.append(i.data)
			break
		count += 1
		for _ in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
	return list


def getT(root, arr, k, lev):
	if not root:
		return
	if lev == k:
		arr.append(root.data)
	if lev > k:
		return
	getT(root.left, arr, k, lev + 1)
	getT(root.right, arr, k, lev + 1)

def KDistance(root, k):
	arr = []
	getT(root, arr, k, 0)
	return arr


def KDistance(root, k):
	from collections import deque
	q = deque()
	d = -1
	result = []
	q.append(root)
	while len(q):
		s = len(q)
		d += 1
		for i in range(s):
			node = q.popleft()
			if d == k:
				result.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
	return result


from collections import deque

def KDistance(root, k):
	q = deque()
	q.append((root, 0))
	ans = []
	while q:
		(node, level) = q.popleft()
		if node is None:
			continue
		if level == k:
			ans.append(node.data)
		elif level > k:
			break
		q.append((node.left, level + 1))
		q.append((node.right, level + 1))
	return ans


def KDistance(root, k):
	if root is None:
		return []
	if k == 0:
		return [root.data]
	que = [root]
	level_counts = []
	res = []
	while que:
		size = len(que)
		count = 0
		for i in range(0, size):
			el = que.pop(0)
			count += 1
			if el.left:
				que.append(el.left)
			if el.right:
				que.append(el.right)
		level_counts.append(count)
		if len(level_counts) == k:
			break
	for node in que:
		res.append(node.data)
	return res


def KDistance(root, k):
	a = []

	def temp(root, k):
		if root:
			if k == 0:
				a.append(root.data)
			else:
				temp(root.left, k - 1)
				temp(root.right, k - 1)
		else:
			return
	temp(root, k)
	return a


def KDistance(root, k):
	if root is None:
		return []
	q = []
	q.append(root)
	counter = -1
	ans = []
	while len(q) > 0:
		t = []
		counter += 1
		while len(q) != 0:
			x = q.pop(0)
			if x.left is not None:
				t.append(x.left)
			if x.right is not None:
				t.append(x.right)
			if counter == k:
				ans.append(x.data)
		q = t
	return ans


def KDistance(root, k):

	def solve(root, k, n, ans):
		if not root:
			return
		if n == k:
			ans.append(root.data)
		solve(root.left, k, n + 1, ans)
		solve(root.right, k, n + 1, ans)
	ans = []
	solve(root, k, 0, ans)
	return ans


def solve(root, k, d, q):
	if root is not None:
		solve(root.left, k, d + 1, q)
		solve(root.right, k, d + 1, q)
		if d == k:
			q.append(root.data)
			return

def KDistance(root, k):
	d = 0
	q = []
	solve(root, k, 0, q)
	return q


def KDistance(root, k):
	q = []
	q.append(root)
	count = 0
	res = []
	flag = 0
	while len(q) != 0:
		size = len(q)
		if count == k:
			flag = 1
			break
		count += 1
		for i in range(size):
			t = q.pop(0)
			if t.left:
				q.append(t.left)
			if t.right:
				q.append(t.right)
	ans = []
	if flag != 1:
		return []
	while len(q) != 0:
		t = q.pop(0)
		ans.append(t.data)
	return ans


def KDistance(root, k):
	if k == 0 and root:
		return [root.data]
	if not root:
		return []
	d = {}
	l = []
	level = 0
	helper(root, level, d, k)
	if k - 1 in d:
		for i in d[k - 1]:
			if i.left and i.right:
				l += [i.left.data]
				l += [i.right.data]
			elif i.left and (not i.right):
				l.append(i.left.data)
			elif i.right and (not i.left):
				l.append(i.right.data)
		return l
	else:
		return []

def helper(root, level, d, k):
	if root:
		if root == 'N':
			return
		elif level == k - 1:
			if level not in d:
				d[level] = [root]
			else:
				d[level].append(root)
		elif level > k - 1:
			return
		else:
			helper(root.left, level + 1, d, k)
			helper(root.right, level + 1, d, k)


def KDistance(root, k):
	q = []
	q.append(root)
	p = 0
	dic = {}
	while q:
		l = len(q)
		lis = []
		for i in range(l):
			temp = q.pop(0)
			if p not in dic:
				dic[p] = [temp.data]
			elif p in dic:
				dic[p].append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		p += 1
	if k in dic:
		return dic[k]
	else:
		return []


def KDistance(root, k):
	ans = []
	if root == None:
		return ans
	q = deque()
	q.appendleft(root)
	c = -1
	while len(q):
		n = len(q)
		c += 1
		for i in range(1, n + 1):
			el = q.pop()
			if c == k:
				ans.append(el.data)
			if el.left:
				q.appendleft(el.left)
			if el.right:
				q.appendleft(el.right)
	return ans


def KDistance(root, k):
	t1 = []
	queue = [root]
	while queue != []:
		t = []
		for i in range(len(queue)):
			curr = queue[0]
			t.append(curr.data)
			if curr.left != None:
				queue.append(curr.left)
			if curr.right != None:
				queue.append(curr.right)
			queue.pop(0)
		t1.append(t)
	if k < len(t1):
		return t1[k]
	return []


def approach1(root, k):
	if root:
		distance = 0
		queue = [(root, distance)]
		ans = []
		while len(queue) > 0:
			(node, d) = queue.pop(0)
			if d == k:
				ans.append(node.data)
			if node.left:
				queue.append((node.left, d + 1))
			if node.right:
				queue.append((node.right, d + 1))
		return ans
	return []

def KDistance(root, k):
	return approach1(root, k)


import collections

def KDistance(root, k):
	a = []

	def get(node, r):
		if node is None:
			return
		if r == 0:
			a.append(node.data)
			return
		get(node.left, r - 1)
		get(node.right, r - 1)
	get(root, k)
	return a


def KDistance(root, k):

	def ok(root, k, x):
		if root == None:
			return
		if k == 0:
			x.append(root.data)
			return
		else:
			ok(root.left, k - 1, x)
			ok(root.right, k - 1, x)
	x = []
	ok(root, k, x)
	return x


class Node:

	def _init_(self, val):
		self.data = val
		self.left = None
		self.right = None

def KDistance(root, k):
	if k == 0 and root:
		return [root.data]
	if not root:
		return []
	d = {}
	l = []
	level = 0
	helper(root, level, d, k)
	if k - 1 in d:
		for i in d[k - 1]:
			if i.left and i.right:
				l += [i.left.data]
				l += [i.right.data]
			elif i.left and (not i.right):
				l.append(i.left.data)
			elif i.right and (not i.left):
				l.append(i.right.data)
		return l
	else:
		return []

def helper(root, level, d, k):
	if root:
		if root == 'N':
			return
		elif level == k - 1:
			if level not in d:
				d[level] = [root]
			else:
				d[level].append(root)
		elif level > k - 1:
			return
		else:
			helper(root.left, level + 1, d, k)
			helper(root.right, level + 1, d, k)


def KDistance(root, k):

	def find(root, c, ans, k):
		if root == None:
			return
		c += 1
		if c == k:
			if root.left:
				ans.append(root.left.data)
			if root.right:
				ans.append(root.right.data)
			return
		find(root.left, c, ans, k)
		find(root.right, c, ans, k)
	ans = []
	c = 0
	if k == 0:
		return [root.data]
	find(root, c, ans, k)
	return ans


def KDistance(root, k):
	q = []
	q.append(root)
	ans = []
	if k == 0:
		ans.append(root.data)
		return ans
	while k:
		ans = []
		for i in range(len(q)):
			temp = q.pop(0)
			if temp.left:
				q.append(temp.left)
				ans.append(temp.left.data)
			if temp.right:
				q.append(temp.right)
				ans.append(temp.right.data)
		k = k - 1
	return ans


def KDistance(root, k):
	d = []
	q = []
	g = {}
	if root == None:
		ans = []
		return ans
	d.append(root)
	q.append(0)
	while len(d) > 0:
		c = d.pop(0)
		m = q.pop(0)
		if m not in g:
			g[m] = [c.data]
		else:
			g[m].append(c.data)
		if c.left != None:
			d.append(c.left)
			q.append(m + 1)
		if c.right != None:
			d.append(c.right)
			q.append(m + 1)
	l = []
	for x in g:
		if k == x:
			return g[x]
	return l


def KDistance(root, k):

	def another(root, k):
		if root == None:
			return
		if k == 0:
			li.append(root.data)
		another(root.left, k - 1)
		another(root.right, k - 1)
	li = []
	another(root, k)
	return li


from collections import deque

def KDistance(root, k):
	queue = deque()
	queue.append((root, 0))
	dic = {}
	while queue:
		(node, l) = queue.popleft()
		if node is None:
			continue
		if l not in dic:
			dic[l] = []
		dic[l].append(node.data)
		queue.append((node.left, l + 1))
		queue.append((node.right, l + 1))
	if k not in dic:
		return []
	return dic[k]


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

def KDistance(root, k):
	ans = []
	DisplayNodesAtDepthk(root, k, ans)
	return ans


def KDistance(root, k):
	if root == None:
		return 0
	q = deque()
	q.append(root)
	l = 0
	lis = []
	while q:
		for i in range(len(q)):
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			if l == k:
				lis.append(node.data)
		l += 1
	return lis


def KDistance(root, k):

	def traversal(root, k):
		if root is None:
			return
		if k == 0:
			a.append(root.data)
		else:
			traversal(root.left, k - 1)
			traversal(root.right, k - 1)
	a = []
	traversal(root, k)
	return a


def KDistance(root, k):

	def currlvl(root, lvl):
		if root is None:
			return
		elif lvl == 0:
			l.append(root.data)
		elif lvl > 0:
			currlvl(root.left, lvl - 1)
			currlvl(root.right, lvl - 1)
	l = []
	currlvl(root, k)
	return l


def KDistance(root, k):

	def traversal(root, k):
		if root == None:
			return None
		if k == 0:
			list1.append(root.data)
		else:
			traversal(root.left, k - 1)
			traversal(root.right, k - 1)
	list1 = []
	traversal(root, k)
	return list1


from collections import deque

class Node:

	def _init_(self, val):
		self.data = val
		self.left = None
		self.right = None

def KDistance(root, k):
	result = []
	q = deque()
	q.append([root, 0])
	while len(q) > 0:
		curr = q.popleft()
		node = curr[0]
		level = curr[1]
		if level == k:
			result.append(node.data)
		if level < k:
			if node.left:
				q.append([node.left, level + 1])
			if node.right:
				q.append([node.right, level + 1])
	return result


def KDistance(root, k):
	q = []
	final = []
	q.append(root)
	q.append('$')
	level = 0
	while len(q) > 0:
		t = q.pop(0)
		if t == '$':
			if len(q) > 0:
				q.append('$')
				level += 1
		else:
			if level == k:
				final.append(t.data)
			if t.left is not None:
				q.append(t.left)
			if t.right is not None:
				q.append(t.right)
	return final


def KDistance(root, k):
	A = []
	x(root, k, A)
	return A

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


def KDistance(root, k):
	q = deque([root])
	l = 0
	arr = []
	while l < k + 1:
		for i in range(len(q)):
			curr = q.popleft()
			if l == k:
				arr.append(curr.data)
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
		l += 1
	return arr


def KDistance(root, k):
	res = []

	def kdist(node, k, res):
		if node == None:
			return
		if k == 0:
			res.append(node.data)
			return
		else:
			kdist(node.left, k - 1, res)
			kdist(node.right, k - 1, res)
	kdist(root, k, res)
	return res


def kdistanceUtil(root, k, nodes):
	if root is None or k < 0:
		return
	if k == 0:
		nodes.append(root.data)
	kdistanceUtil(root.left, k - 1, nodes)
	kdistanceUtil(root.right, k - 1, nodes)

def KDistance(root, k):
	nodes = []
	kdistanceUtil(root, k, nodes)
	return nodes


def KDistance(root, k):
	arr = []
	ItemsFromLevel(root, k, 0, arr)
	return arr

def ItemsFromLevel(root, k, level, arr):
	if root is None:
		return
	if k == level:
		arr.append(root.data)
	level += 1
	ItemsFromLevel(root.left, k, level, arr)
	ItemsFromLevel(root.right, k, level, arr)
	return


import collections

def utilKDistance(root, k, result):
	if root is None:
		return
	if k == 0:
		result.append(root.data)
	else:
		utilKDistance(root.left, k - 1, result)
		utilKDistance(root.right, k - 1, result)
	return result

def KDistance(root, k):
	result = []
	if root is None:
		return
	return utilKDistance(root, k, result)


def KDistance(root, k):
	k += 1
	res = []
	dist(root, k, res)
	return res

def dist(root, k, res):
	if root:
		k -= 1
		if k:
			dist(root.left, k, res)
			dist(root.right, k, res)
		else:
			res.append(root.data)