Explore
Placement Prep

Edit

Edit

# Find all the nodes at k distance from the root | FACE Prep

Published on 10 Mar 2020

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

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++

Output
Input - Enter the number of edges : 7 Input the tree : 15 12 l 12 8 l 12 13 r 15 18 r 18 24 r 24 22 l 24 27 r Output - Inorder tree traversal : 8 12 13 15 18 22 24 27 Enter the level : 2 Node at level 2 : 8 13 24

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

Output
Input - Enter the number of edges : 7 Input the tree : 15 12 l 12 8 l 12 13 r 15 18 r 18 24 r 24 22 l 24 27 r Output - Inorder tree traversal : 8 12 13 15 18 22 24 27 Enter the level : 2 Node at level 2 : 8 13 24

Time complexity: O(n)

Recommended Programs