Find all the nodes at k distance from the root | faceprep

Program to find all the nodes at k distance from the root in a binary tree is discussed here. Given a binary tree, print all the nodes which are at k distance from the root.

For example, consider the tree given below.

              15
            /   \
          12     18
         /  \    / 
        8   13  24
/ \
22 27
  • Nodes at level 0: 15
  • Nodes at level 1: 12, 18
  • Nodes at level 2: 8, 13, 24
  • Nodes at level 3: 22, 27

find all the nodes at k distance from the root

Solution to this problem can be provided in two different ways.

Method 1: Iterative approach to find all the nodes at k distance from the root.

Method 2: Recursive approach to find all the nodes at k distance from the root.

Algorithm to find all the nodes at K distance from the root (Iterative approach)

  • Input the tree from the user.
  • Initialize level = 1.
  • Push root inside the queue and increment level.
  • In the same way, find the level of the node and push them inside the queue.
  • When the kth level has to be printed, dequeue and print the elements at the kth level from the queue.

Iterative program to find all the nodes at K distance from the root is given below.

// C++ program to find all the nodes at K distance from the root

# include<bits/stdc++.h>
# include
using namespace std;

// Structure to create a tree
struct node
{
int data;
struct node *left;
struct node *right;
};

struct node *newNode(int data)
{
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
};

// Function to print nodes of given level
bool print_nodes_k_Distance(node* root, int klevel)
{
queue<node*> q;
int level = 1;
bool flag = false;
q.push(root);

// keep track of all the nodes to be pushed before level is incremented by 1
q.push(NULL);
while (!q.empty()) {
node* temp = q.front();

// print when level is equal to k
if (level == klevel && temp != NULL) {
flag = true;
cout << temp->data << ” “;
}
q.pop();
if (temp == NULL) {
if (q.front())
q.push(NULL);
level += 1;

// quit the loop if level exceed the given level number
if (level > klevel)
break;
} else {
if (temp->left)
q.push(temp->left);

if (temp->right)
q.push(temp->right);
}
}
cout << endl;

return flag;
}

void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}

// Function that prints the inorder traversal of the tree
void inorder(struct node *root)
{
if(root == NULL)
return;
inorder(root -> left);
cout << root -> data << ” “;
inorder(root -> right);
}

int main()
{
struct node *root = NULL;
int n;
cout << “\nEnter the number of edges : “;
cin >> n;
cout << “\nInput the tree : \n”;
while(n–)
{
char lr;
int n1,n2;
cin >> n1;
cin >> n2;
cin >> lr;
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
cout << “\nInorder Tree Traversal : “;
inorder(root);
cout << endl;
cout <<“\nEnter the level : “;
cin >> level;
print_nodes_k_Distance(root,level);
cout << endl;
return 0;
}

Algorithm to find all the nodes at K distance from the root (Recursive approach)

print_nodes_k_Distance( node *root, k ) 

  1. if(root == NULL)
  2. return;
  3. if( k == 0 )
  4. print (root->data)
  5. else
  6. recursively call the function print_nodes_k_Distance( root->left, k – 1 )  // left subtree.
  7. recursively call the function print_nodes_k_Distance( root->right, k – 1 ) // right subtree.

Recursive program to find all the nodes at K distance from the root is given below.

// C++ program to find all the nodes at K distance from the root

# include<bits/stdc++.h>
# include<stdlib.h>
using namespace std;

// Structure to create a tree
struct node
{
int data;
struct node *left;
struct node *right;
};

struct node *newNode(int data)
{
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
};

void print_nodes_k_Distance(node *root , int k)
{
if(root == NULL)
return;

if( k == 0 )
{
cout << root->data << ” “;
return ;
}
else
{
print_nodes_k_Distance( root->left, k – 1 ) ;
print_nodes_k_Distance( root->right, k – 1 ) ;
}
}


void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}

// Function that prints the inorder traversal of the tree
void inorder(struct node *root)
{
if(root == NULL)
return;
inorder(root -> left);
cout << root -> data << ” “;
inorder(root -> right);
}

int main()
{
struct node *root = NULL;
int n;
cout << “\nEnter the number of edges : “;
cin >> n;
cout << “\nInput the tree : \n”;
while(n–)
{
char lr;
int n1,n2;
cin >> n1;
cin >> n2;
cin >> lr;
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
cout << “\nInorder Tree Traversal : “;
inorder(root);
cout << endl;
int level;
cout <<“\nEnter the level : “;
cin >> level;
print_nodes_k_Distance(root,level);
cout << endl;
return 0;
}