Table of Contents
Given a Binary Tree and an integer value K, write a function to print all the nodes that are at a distance K from the root node.
Consider the following Binary Tree:
5
/ \
3 8
/ \ / \
2 4 6 10
Given K = 2, the nodes at distance 2 from the root are {2, 4, 6, 10}.
Expected Output:
Nodes at distance 2 from root: 2 4 6 10
Time and Space Complexity:
The time complexity of printing nodes at K distance from the root in a Binary Tree is O(n), where n is the number of nodes in the tree. This is because we need to visit every node once.
The space complexity is O(h), where h is the height of the tree, due to the space used by the recursive function call stack.
C++ Solution:
#include <iostream>
// Define a node structure for the Binary Tree
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
// Function to print nodes at K distance from root
void printNodesAtKDistance(Node* root, int k) {
if (root == nullptr)
return;
if (k == 0) {
std::cout << root->data << " ";
return;
}
// Recursively print nodes at K distance in left and right subtrees
printNodesAtKDistance(root->left, k - 1);
printNodesAtKDistance(root->right, k - 1);
}
int main() {
// Creating the Binary Tree
Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(8);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->right->left = new Node(6);
root->right->right = new Node(10);
int k = 2;
// Print nodes at distance K from the root
std::cout << "Nodes at distance " << k << " from root: ";
printNodesAtKDistance(root, k);
std::cout << std::endl;
return 0;
}
Code Explanation:
- We define a Node structure for the Binary Tree, holding data, a left child, and a right child.
- The printNodesAtKDistance function recursively prints nodes at distance K from the root. If K is 0, it prints the data of the current node. Otherwise, it recursively calls itself for the left and right subtrees with K decremented by 1.
- In the main function, we create the Binary Tree, specify K, and call printNodesAtKDistance to print the nodes at distance K from the root.
When you run the code with K = 2, it prints the nodes {2, 4, 6, 10} which are at distance 2 from the root.
Output:
Nodes at distance 2 from root: 2 4 6 10