# Finding all Node of k Distance in a Binary Tree

## 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: 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: 