Link copied to clipboard. Share away!

Dismiss

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.

- 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

**print_nodes_k_Distance( node *root, k )**

- if(root == NULL)
- return;
- if( k == 0 )
- print (root->data)
- else
- recursively call the function print_nodes_k_Distance( root->left, k - 1 ) // left subtree.
- 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*

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×