Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Recursive Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
How do you find the distance of nodes??
3.2.
What is the level in a binary tree?
3.3.
What is the binary tree used for?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Print nodes at k distance from root

Introduction

Data structure and algorithms are one of the most important topics to understand if you want to prepare for a top product-based company. In this blog, we will take a quick look at the problem statement and discuss the recursion technique to solve the problem of printing the nodes at a k distance from the root. Here we are using the recursion to tackle the problem.

Problem Statement

Given a tree's root and integer k, print all nodes at a distance of k from the root.

Sample Examples

Example 1

Input

Enter the K value: 1

 

Output

The Nodes are : 3 4

Explanation

For K= 1, we have 3, 4 at distance 1.

 

Example 2

Input

Enter the K value: 2

Output

The Nodes are : 5 6 7 8

Explanation

For K= 2, we have 5, 6, 7, and 8 at distance 2.

Recursive Approach

The method is straightforward: First, we accept the root node and k as input arguments to the function and check until k=0 is encountered. As soon as it is encountered, the value in the current node will be printed. Let's have a look at the algorithm and how it works.

Algorithm

  1. Make a recursion function, let's say Klevel(node * root, int k).
     
  2. With a distance of k-1, this function will recursively call itself in its left and right children.
     
  3. Finally, if k=0 is encountered, the value in the current node will be printed. The root will be k nodes away from this node.

Implementation in C++

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

class Node
{
    public:
    int data;
    Node* left, *right;
    
    // allocates new node with data and NULL left,right pointers
    Node(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

void Klevel(Node *Root , int k)
{
    if(Root == NULL|| k < 0 )
        return;
    if( k == 0 )
    {
        cout << Root->data << " ";
        return;
    }
        //left recursion
        Klevel( Root->left, k - 1 ) ;
        //right recursion
        Klevel( Root->right, k - 1 ) ;
  
}

int main()
{
    int k;
    cout<<"Enter the K value: ";
    cin>>k;
    Node *root = new Node(2);
    root->left = new Node(3);
    root->right = new Node(4);
    root->left->left = new Node(5);
    root->left->right = new Node(6);
    root->right->left = new Node(7);

    cout<<"The Nodes are : ";
    
    Klevel(root, k);
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Input

Enter the K value: 1

 

Output

The Nodes are : 3 4

Time Complexity

Time complexity is O(n), where ‘n’ is the number of nodes in a binary tree.

Space Complexity

The space complexity will be O(height of the tree) as the maximum depth of the recursion stack can be the height of the tree.

Must Read Recursion in Data Structure

Frequently Asked Questions

How do you find the distance of nodes??

In terms of the lowest common ancestor, the distance between two nodes can be determined. Distance(n1, n2) = Distance(root, n1) + Distance(root, n2) - 2*Distance(root, LCA) 'n1' and 'n2' are the two given keys 'root' is root of given Binary Tree.
 

What is the level in a binary tree?

The root node is the topmost node in a binary tree. The number of edges along the unique path between a node and the root node determines its level.
 

What is the binary tree used for?

Binary trees are mostly utilized in computing for searching and sorting since they allow data to be stored hierarchically. Insertion, deletion, and traversal are some of the most popular operations on binary trees.

Conclusion

This article extensively discussed the problem of printing the nodes at a k distance from the root. We solved the problem using the recursion and discussed time as well as space complexity.

We hope that this blog has helped you enhance your knowledge about the above question and recursion technique. If you would like to learn more, check out our articles Level Order Traversal Of  A Binary TreeRecursion, also do check our notes Recursion Notes and many more on our Website.

Recommended Problems:

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass