Given a Binary Tree and a positive integer k. The task is to count all distinct nodes that are distance k from a leaf node. A node is at k distance from a leaf if it is present k levels above the leaf and also, is a direct ancestor of this leaf node. If k is more than the height of Binary Tree, then nothing should be counted.
Example 1:
Input:
        1
      /   \
     2     3
   /  \   /  \
  4   5  6    7
          \ 
          8
K = 2
Output: 2
Explanation: There are only two unique
nodes that are at a distance of 2 units
from the leaf node. (node 3 for leaf
with value 8 and node 1 for leaves with
values 4, 5 and 7)
Note that node 2
isn't considered for leaf with value
8 because it isn't a direct ancestor
of node 8.
Example 2:
Input:
          1
         /
        3
       /
      5
    /  \
   7    8
         \
          9
K = 4
Output: 1
Explanation: Only one node is there
which is at a distance of 4 units
from the leaf node.(node 1 for leaf
with value 9) 
Your Task:
You don't have to read input or print anything. Complete the function printKDistantfromLeaf() that takes root node and k as inputs and returns the number of nodes that are at distance k from a leaf node. Any such node should be counted only once. For example, if a node is at a distance k from 2 or more leaf nodes, then it would add only 1 to our count.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

@input - 

node - root node of given tree

k = distance of nodes required 



class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''



#Function to return count of nodes at a given distance from leaf nodes.

def printKDistantfromLeaf(root, k):

    #code here

Solutions:
def printKDistantfromLeaf(root, k):
	lis = []
	se = set()

	def fun(root):
		if root == None:
			return
		lis.append(root)
		if root.left == None and root.right == None:
			dis = len(lis) - k - 1
			if dis >= 0:
				se.add(lis[dis])
			lis.pop()
			return
		fun(root.left)
		fun(root.right)
		lis.pop()
	fun(root)
	return len(se)


def util(root, k, parentDic):
	global ansDic
	if root == None:
		return
	if root.left == None and root.right == None:
		node = root
		i = 0
		while parentDic.get(node) != None and i < k:
			node = parentDic[node]
			i += 1
		if i == k:
			ansDic[node] = 1
		return
	util(root.left, k, parentDic)
	util(root.right, k, parentDic)

def printKDistantfromLeaf(root, k):
	parentDic = {}
	q = [root]
	while len(q) > 0:
		temp = q[0]
		q.pop(0)
		if temp.left != None:
			q.append(temp.left)
			parentDic[temp.left] = temp
		if temp.right != None:
			q.append(temp.right)
			parentDic[temp.right] = temp
	global ansDic
	ansDic = {}
	util(root, k, parentDic)
	return len(ansDic)


def check(root, k):
	if root is None:
		return False
	if not root.left and (not root.right):
		if k == 0:
			return True
		else:
			return False
	return check(root.left, k - 1) or check(root.right, k - 1)

def printKDistantfromLeaf(root, k):
	s = set()

	def recursive(root, k):
		if root is None:
			return
		if check(root, k):
			s.add(root)
		recursive(root.left, k)
		recursive(root.right, k)
	recursive(root, k)
	return len(s)


def printKDistantfromLeaf(root, k):
	s = set()

	def solve(root, ans):
		if not root:
			return
		if not root.left and (not root.right):
			if len(ans) >= k:
				s.add(ans[len(ans) - k])
			return
		ans.append(root)
		solve(root.left, ans)
		solve(root.right, ans)
		ans.pop()
		return
	solve(root, [])
	return len(s)


def preorderTraversal(root, k, preorder, ans):
	if root is None:
		return
	if root.left is None and root.right is None:
		if len(preorder) >= k:
			size = len(preorder)
			ans.add(preorder[size - k])
		return
	preorder.append(root)
	preorderTraversal(root.left, k, preorder, ans)
	preorderTraversal(root.right, k, preorder, ans)
	preorder.pop()
	return

def printKDistantfromLeaf(root, k):
	preorder = []
	ans = set()
	preorderTraversal(root, k, preorder, ans)
	return len(ans)


def printKDistantfromLeafUtil(root, k, result, visited):
	if root is None:
		return
	visited.append(root)
	if root.left is None and root.right is None:
		if k < len(visited):
			result.add(visited[-k - 1])
	else:
		printKDistantfromLeafUtil(root.left, k, result, visited)
		printKDistantfromLeafUtil(root.right, k, result, visited)
	visited.pop()

def printKDistantfromLeaf(root, k):
	result = set()
	visited = []
	printKDistantfromLeafUtil(root, k, result, visited)
	return len(result)


def printKDistantfromLeaf(root, k):
	out = set()

	def dfs(root, temp=''):
		if not root:
			return
		if not root.left and (not root.right):
			temp += str(root)
			out.add(temp)
			return
		temp += str(root) + ','
		dfs(root.left, temp)
		dfs(root.right, temp)
	dfs(root)
	res = set()
	for i in out:
		i = i.split(',')
		if len(i) - 1 - k >= 0:
			res.add(i[len(i) - 1 - k])
	return len(res)


class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None
ans = []

def printKDistantfromLeaf(root, k):
	lis = []
	se = set()

	def fun(root):
		if root == None:
			return
		lis.append(root)
		if root.left == None and root.right == None:
			dis = len(lis) - k - 1
			if dis >= 0:
				se.add(lis[dis])
			lis.pop()
			return
		fun(root.left)
		fun(root.right)
		lis.pop()
	fun(root)
	return len(se)


def printKDistantfromLeaf(root, k):
	booli = []
	res = []
	curr = []
	knode(root, k, booli, curr, 0, res)
	return len(res)

def knode(root, k, booli, curr, count, res):
	if root is None:
		return
	booli.append(False)
	curr.append(root.data)
	if root.left is None and root.right is None and (count - k >= 0) and (booli[count - k] == False):
		res.append(curr[count - k])
		booli[count - k] = True
	knode(root.left, k, booli, curr, count + 1, res)
	knode(root.right, k, booli, curr, count + 1, res)
	booli.pop()
	curr.pop()


def printKDistantfromLeaf(root, k):
	global c
	c = 0
	visited = [0] * MAX_HEIGHT
	printKDistantfromLeafUtil(root, visited, 0, k)
	return c

def printKDistantfromLeafUtil(node, visited, pathLen, k):
	global c
	if node == None:
		return
	visited[pathLen] = 0
	pathLen += 1
	if node.left == None and node.right == None and (pathLen - k - 1 >= 0) and (visited[pathLen - k - 1] == 0):
		c += 1
		visited[pathLen - k - 1] = 1
		return
	printKDistantfromLeafUtil(node.left, visited, pathLen, k)
	printKDistantfromLeafUtil(node.right, visited, pathLen, k)


def solve(node, k, ans):
	if not node:
		return set([0])
	if not node.left and (not node.right):
		return set([1])
	left = set()
	right = set()
	if node.left:
		left = solve(node.left, k, ans)
	if node.right:
		right = solve(node.right, k, ans)
	res = left.union(right)
	res = set([a + 1 for a in res])
	if k + 1 in res:
		ans[0] += 1
	return res

def printKDistantfromLeaf(root, k):
	ans = [0]
	solve(root, k, ans)
	return ans[0]