Implementation

#include <iostream>
using namespace std;


// creating a brand-new binary tree node.
struct __nod
{
	int record;
	struct __nod *Lft, *Rt;
};


/* creating a new recursive function that will help us print all the nodes at the distance of k in the subtree and with a given root. 
See */
void printkdistance__nodDown(__nod *root, int k)
{
	// writing the basic case
	if (root == NILL || k < 0) return;


	//If we arrive at node k, we have to print it.
	if (k==0)
	{
		cout << root->record << endl;
		return;
	}


	// we have to perform the recursion function for the left and right subtrees
	printkdistance__nodDown(root->Lft, k-1);
	printkdistance__nodDown(root->Rt, k-1);
}


// Now, we will print all the nodes at the distance of k from the target node; the k distance node might be upward or downward. Then the given function might be able to return the distance from the target node; if it returns the value -1, then the target is not present in the root node.  
int printkdistance__nod(__nod* root, __nod* target , int k)
{
	// the basic case is if the tree is empty, we have to return the -1 value. 
	if (root == NILL) return -1;


	// In case the target is the same as the root element, we have to use the downward function and print all the nodes at the distance of k in the subtree, which is supposed to be rooted at with the target or the root. 
	if (root == target)
	{
		printkdistance__nodDown(root, k);
		return 0;
	}


	// we have to perform recursion at the left subtree
	int dl = printkdistance__nod(root->Lft, target, k);


	// verify if the target node was found in the left subtree. 
	if (dl != -1)
	{
		// In case the root is at a distance of k from the allotted target, then we have to print the root of the node and keep in mind that 
dl is the Distance of the root's Lft child from the target
		if (dl + 1 == k)
			cout << root->record << endl;


		// otherwise, we must commute to the right subtree and print all the k-dl nodes. 
		// Note that the Rt child is two edges away from the left child
		else
			printkdistance__nodDown(root->Rt, k-dl-2);


		// Add 1 to the distance and return value for parent calls
		return 1 + dl;
	}


	// MIRROR OF THE ABOVE CODE FOR THE RIGHT SUBTREE
	int dr = printkdistance__nod(root->Rt, target, k);
	if (dr != -1)
	{
		if (dr + 1 == k)
			cout << root->record << endl;
		else
			printkdistance__nodDown(root->Lft, k-dr-2);
		return 1 + dr;
	}


	// In case the target was not present in either of them, such as the left and right subtree.
	return -1;
}


// Creating a new utility function to create a new binary tree node.
__nod *new__nod(int record)
{
	__nod *temp = nw __nod;
	temp->record = record;
	temp->Lft = temp->Rt = NILL;
	return temp;
}


// writing the main drivers program to test the above functions
int main()
{
	/* Let us construct the tree shown in the above diagram */
	__nod * root = new__nod(20);
	root->Lft = new__nod(8);
	root->Rt = new__nod(22);
	root->Lft->Lft = new__nod(4);
	root->Lft->Rt = new__nod(12);
	root->Lft->Rt->Lft = new__nod(10);
	root->Lft->Rt->Rt = new__nod(14);
	__nod * target = root->Lft->Rt;
	printkdistance__nod(root, target, 2);
	return 0;
}

Output:

Finding All Node of k Distance in a Binary Tree

Example 2

// Writing a Java program to print all the nodes present at the k distance from the given node. 


// creating a brand-new binary tree node.
class __nod
{
	int record;
	__nod Lft, Rt;


	__nod(int item)
	{
		record = item;
		Lft = Rt = NILL;
	}
}


class BinaryTree
{
	__nod root;
	/* creating a new recursive function that will help us print all the nodes at the distance of k in the subtree and with a given root. 
See */


	void printkdistance__nodDown(__nod __nod, int k)
	{
		// writing the basic case
		if (__nod == NILL || k < 0)
			return;


	// In case we have arrived at node k, then we have to print it.
		if (k == 0)
		{
			System.out.print(__nod.record);
			System.out.println("");
			return;
		}


	// we have to perform the recursion function for the left and right subtrees
		printkdistance__nodDown(__nod.Lft, k - 1);
		printkdistance__nodDown(__nod.Rt, k - 1);
	}
// Now, we will print all the nodes at the distance of k from the target node, and the k distance node might be upward or downward. Then the given function might be able to return the distance from the target node; if it returns the value -1, then the target is not present in the root node.  
	int printkdistance__nod(__nod __nod, __nod target, int k)
	{
	// In case the target is the same as the root element, we have to use the downward function and print all the nodes at the distance of k in the subtree, which is supposed to be rooted at with the target or the root. 


		if (__nod == NILL)
			return -1;
 
	// In case the root is at a distance of k from the allotted target, then we have to print the root of the node and keep in mind that 
dl is the Distance of the root's Lft child from the target
		if (__nod == target)
		{
			printkdistance__nodDown(__nod, k);
			return 0;
		}


	// we have to perform recursion at the left subtree
		int dl = printkdistance__nod(__nod.Lft, target, k);


		// verify if the target node was found in the left subtree. 
		if (dl != -1)
		{
			// In case the root is at a distance of k from the allotted target, then we have to print the root of the node and keep in mind that 
dl is the Distance of the root's Lft child from the target
			if (dl + 1 == k)
			{
				System.out.print(__nod.record);
				System.out.println("");
			}
					// otherwise, we must commute to the right subtree and print all the k-dl nodes. 
				printkdistance__nodDown(__nod.Rt, k - dl - 2);


			// Note that the Rt child is two edges away from the left child
			return 1 + dl;
		}


		// MIRROR OF ABOVE CODE FOR RT SUBTREE
			// In case the target was not present in either of them, such as the left and right subtree.
		int dr = printkdistance__nod(__nod.Rt, target, k);
		if (dr != -1)
		{
			if (dr + 1 == k)
			{
				System.out.print(__nod.record);
				System.out.println("");
			}
			else
				printkdistance__nodDown(__nod.Lft, k - dr - 2);
			return 1 + dr;
		}


// Creating a new utility function to create a new binary tree node.
		return -1;
	}
// writing the main drivers program to test the above functions


	public static void main(String args[])
	{
		BinaryTree tree = new BinaryTree();


		/* Let us construct the tree shown in the above diagram */
		tree.root = nw __nod(20);
		tree.root.Lft = nw __nod(8);
		tree.root.Rt = nw __nod(22);
		tree.root.Lft.Lft = nw __nod(4);
		tree.root.Lft.Rt = nw __nod(12);
		tree.root.Lft.Rt.Lft = nw __nod(10);
		tree.root.Lft.Rt.Rt = nw __nod(14);
		__nod target = tree.root.Lft.Rt;
		tree.printkdistance__nod(tree.root, target, 2);
	}
}

Output:

Example 3

// Writing a Python program in-order to print all the nodes present at the k distance from the given node. 
// creating a brand-new binary tree node.
class __nod:
	# A constructor to create a new node
	def __init__(self, record):
		self.record = record
		self.Lft = None
		self.Rt = None
	
/* creating a new recursive function that will help us print all the nodes at the distance of k in the subtree and with a given root. 
See */
def printkDistance__nodDown(root, k):
	// writing the basic case
	if the root is None or k< 0 :
		return
// In case we have arrived at node k, then we have to print it.	
	if k == 0 :
		print (root.record)
		return
// we have to perform the recursion function for the left and right subtrees
	printkDistance__nodDown(root.Lft, k-1)
	printkDistance__nodDown(root.Rt, k-1)
// Now, we will print all the nodes at the distance of k from the target node; the k distance node might be upward or downward. Then the given function might be able to return the distance from the target node; if it returns the value -1, then the target is not present in the root node.  		
def printkDistance__nod(root, target, k):
	
	# Base Case 1: IF tree is empty, return -1
	If the root is None:
		return -1
// In case the target is the same as the root element, we have to use the downward function and print all the nodes at the distance of k in the subtree, which is supposed to be rooted at with the target or the root. 
	if root == target:
		printkDistance__nodDown(root, k)
		return 0
	// we have to perform recursion at the left subtree
	dl = printkDistance__nod(root.Lft, target, k)
	// verify if the target node was found in the left subtree. 
	if dl != -1:
	// In case the root is at a distance of k from the allotted target, then we have to print the root of the node and keep in mind that 
dl is the Distance of the root's Lft child from the target			
		if dl +1 == k :
			print (root.record)
			// otherwise, we must commute to the right subtree and print all the k-dl nodes. 
		// Note that the Rt child is two edges away from the left child
		Else:
			printkDistance__nodDown(root.Rt, k-dl-2)


		# Add 1 to the distance and return the value for
		# for parent calls
		return 1 + dl


	# MIRROR OF THE ABOVE CODE FOR THE RIGHT SUBTREE
	# Note that we reach here only when the node was not found anywhere and also in the right subtree
	dr = printkDistance__nod(root.Rt, target, k)
	if dr != -1:
		if (dr+1 == k):
			print (root.record)
		else:
			printkDistance__nodDown(root.Lft, k-dr-2)
		return 1 + dr
// In case the target was not present in either of them, such as the left and right subtree.
	return -1


// writing the main drivers program to test the above functions
root = __nod(20)
root.Lft = __nod(8)
root.Rt = __nod(22)
root.Lft.Lft = __nod(4)
root.Lft.Rt = __nod(12)
root.Lft.Rt.Lft = __nod(10)
root.Lft.Rt.Rt = __nod(14)
target = root.Lft.Rt
printkDistance__nod(root, target, 2)

Output:

Example 4

<script>
// Writing a Javascript program in-order to print all the nodes present at the k distance from the given node. 
// creating a brand-new binary tree node.
class __nod
{
	constructor(item)
	{
		this.record = item;
		this.Lft = NILL;
		this.Rt = NILL;
	}
}


var root = NILL;


/* creating a new recursive function that will help us print all the nodes at the distance of k in the subtree and with a given root. 
See */
function printkdistance__nodDown(__nod, k)
{
	// writing the basic case
	if (__nod == NILL || k < 0)
	{
		return;
	}
//If we arrive at node k, we have to print it.
	if (k == 0)
	{
		document.write(__nod.record);
		document.write("<br>");
		return;
	}
	// we have to perform the recursion function for the left and right subtrees
	printkdistance__nodDown(__nod.Lft, k - 1);
	printkdistance__nodDown(__nod.Rt, k - 1);
}
// Now, we will print all the nodes at the distance of k from the target node; the k distance node might be upward or downward. Then the given function might be able to return the distance from the target node; if it returns the value -1, then the target is not present in the root node.  
function printkdistance__nod(__nod, target, k)
{
	// Base Case 1: If the tree is empty, return -1
	if (__nod == NILL)
	{
		return -1;
	}
		// In case the target is the same as the root element, we have to use the downward function and print all the nodes at the distance of k in the subtree, which is supposed to be rooted at with the target or the root. 
	if (__nod == target)
	{
		printkdistance__nodDown(__nod, k);
		return 0;
	}
		// we have to perform recursion at the left subtree
	var dl = printkdistance__nod(__nod.Lft, target, k);
// verify if the target node was found in the left subtree. 


	if (dl != -1)
	{
			// In case the root is at a distance of k from the allotted target, then we have to print the root of the node and keep in mind that 
dl is the Distance of the root's Lft child from the target
		if (dl + 1 == k)
		{
			document.write(__nod.record);
			document.write("<br>");
		}
			// otherwise, we have to commute to the right subtree and print all the k-dl nodes.
		else
		{
			printkdistance__nodDown(__nod.Rt, k - dl - 2);
		}
		// Add 1 to the distance and return value for parent calls
		return 1 + dl;
	}
	// MIRROR OF THE ABOVE CODE FOR THE RIGHT SUBTREE
	// Note that we reach here only when the node was not found in left
	// subtree
	var dr = printkdistance__nod(__nod.Rt, target, k);
	if (dr != -1)
	{
		if (dr + 1 == k)
		{
			document.write(__nod.record);
			document.write("<br>");
		}
		else
		{
			printkdistance__nodDown(__nod.Lft, k - dr - 2);
		}
		return 1 + dr;
	}
	// In case the target was not present in either of them, such as the left and right subtree.
	return -1;
}
// writing the main drivers program to test the above function
/* Let us construct the tree shown in the above diagram */
root = nw __nod(20);
root.Lft = nw __nod(8);
root.Rt = nw __nod(22);
root.Lft.Lft = nw __nod(4);
root.Lft.Rt = nw __nod(12);
root.Lft.Rt.Lft = nw __nod(10);
root.Lft.Rt.Rt = nw __nod(14);
var target = root.Lft.Rt;
printkdistance__nod(root, target, 2);
</script>

Output:

Data Structures Tutorial

Misc Topic:

Data Structures Tutorial

Misc Topic:

Finding all Node of k Distance in a Binary Tree

Implementation