Question:

How to count the number of special nodes using Python3

Summary

Let’s assume:

Methods: printKDistantfromLeaf

The method will allow us to count the number of nodes at a given distance ‘k’ from leaf nodes in a binary tree.

Solution

#User function Template for python3

class Solution:

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

def printKDistantfromLeaf(self, root, k):

vis=set()

self.dfs(root,[],k,vis)

return len(vis)

def dfs(self,root,stack,k,vis):

if root:

stack.append(root)

if not root.left and not root.right:

n=len(stack)

if n>k and (stack[-k-1] not in vis):

vis.add(stack[-k-1])

self.dfs(root.left,stack,k,vis)

self.dfs(root.right,stack,k,vis)

stack.pop()

Explanation

The binary tree's root, root, and the distance from leaf nodes to count nodes, k, are the two parameters required by the printKDistantfromLeaf function.
A set named vis is initialized inside printKDistantfromLeaf to record visited nodes.
With the parameters root, stack, k, and vis, the depth-first search method, or dfs, is called. The binary tree is traversed depth-first by this function.