(94). 27.14. NODES AT DISTANCE K IN BINARY TREE. - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki
//Nodes at Distance K in Binary Tree
#include <bits/stdc++.h> using namespace std;
struct Node{ int data; struct Node* left; struct Node* right;
Node(int val){
data = val;
left = NULL;
right = NULL;
}
};
//case 1: void printSubtreeNodes(Node* root, int k){ if(root == NULL || k<0){ return; } if(k == 0){ cout << root->data <<" "; return; }
printSubtreeNodes(root->left, k-1);
printSubtreeNodes(root->right, k-1);
}
//case 2: int printNodesAtk(Node root, Node target, int k){ if(root == NULL){ return -1; } if(root == target){ printSubtreeNodes(root, k); return 0; }
//for left child
int dl = printNodesAtk(root->left,target, k);
if(dl != -1){
if(dl + 1 == k){
cout << root->data <<" ";
}
else{
printSubtreeNodes(root->right, k-dl-2);
}
return 1 + dl;
}
//for right child
int dr = printNodesAtk(root->right, target, k);
if(dr != -1){
if(dr + 1 == k){
cout << root->data <<" ";
}
else{
printSubtreeNodes(root->left, k-dr-2);
}
return 1 + dr;
}
return -1;
}
int main(){
/*
1
/ \
2 3
/ 4 */
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
cout << "Nodes at distance k: "; printNodesAtk(root, root->left, 1); // 2 ke 1 distance pr 4 or 1 hai.
return 0;
}
/* OUTPUT: Nodes at distance k: 4 1 */