Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




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

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

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






If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises