In this tutorial we shall see how to print all the nodes that is k distance from root.
Problem statement:
Given the root node and the distance k, print all the nodes that are at distance k from root node.
Consider the image below:
So according to the image, root is at level 0, below that is level 1 etc.
So if the k value is 3, then you need to print h, i, j, k.
If the k value is 1, you need to print b, c.
So how do we solve this?
First base cases will be:
- If the node becomes null, then we return.
- If the k value becomes 0, we return the value pointed by the node.
Then we make a recursive call to both left and right child. While doing a recursive call, we decrease the k value.
Pseudo Code:
void get_k_node(node *p, int k)
{
if (p == NULL)
return ;
if (k == 0)
print p -> value
else
{
get_k_node(p->left)
get_k_node(p->right)
}
}
The recursion tree when k = 2 will be like below:
Solution in C++
#include <iostream> #include <stack> #include <vector> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; void get_k_node(Node *node, int k) { if (node == NULL) return ; if (k == 0) cout<< node -> data<<" "; else { get_k_node(node->left, k-1); get_k_node(node->right, k-1); } } int main() { Node* root = nullptr; /* Binary tree: 16 / \ / \ 10 25 / \ / \ / \ / \ 7 15 18 30 */ root = new Node(16); root->left = new Node(10); root->right = new Node(25); root->left->left = new Node(7); root->left->right = new Node(15); root->right->left = new Node(18); root->right->right = new Node(30); get_k_node(root, 2); return 0; }
Output:
7 15 18 30