सी ++ में बाइनरी ट्री में निकटतम पत्ता खोजें

मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें विभिन्न स्तरों पर पत्ती की गांठें होती हैं। एक और पॉइंटर दिया गया है, जो एक नोड की ओर इशारा कर रहा है। हमें नुकीले नोड से निकटतम लीफ नोड की दूरी ज्ञात करनी होगी। विचार करें कि पेड़ नीचे जैसा है -

यहां लीफ नोड्स 2, -2 और 6 हैं। यदि पॉइंटर नोड -5 की ओर इशारा कर रहा है, तो -5 से निकटतम नोड्स दूरी 1 पर होंगे।

इसे हल करने के लिए, हम दिए गए नोड के साथ रूट किए गए सबट्री को पार करेंगे, और सबट्री में निकटतम पत्ता ढूंढेंगे, फिर दूरी को स्टोर करेंगे। अब रूट से शुरू होकर ट्रैवर्सिंग ट्री, अगर नोड x लेफ्ट सबट्री में मौजूद है, तो राइट सबट्री में सर्च करें, और इसके विपरीत।

उदाहरण

#include<iostream>
using namespace std;
class Node {
   public:
      int data;
   Node *left, *right;
};
Node* getNode(int data) {
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return node;
}
void getLeafDownward(Node *root, int level, int *minDist) {
   if (root == NULL)
      return ;
   if (root->left == NULL && root->right == NULL) {
      if (level < (*minDist))
         *minDist = level;
      return;
   }
   getLeafDownward(root->left, level+1, minDist);
   getLeafDownward(root->right, level+1, minDist);
}
int getFromParent(Node * root, Node *x, int *minDist) {
   if (root == NULL)
      return -1;
   if (root == x)
      return 0;
   int l = getFromParent(root->left, x, minDist);
   if (l != -1) {
      getLeafDownward(root->right, l+2, minDist);
      return l+1;
   }
   int r = getFromParent(root->right, x, minDist);
   if (r != -1) {
      getLeafDownward(root->left, r+2, minDist);
      return r+1;
   }
   return -1;
}
int minimumDistance(Node *root, Node *x) {
   int minDist = INT8_MAX;
   getLeafDownward(x, 0, &minDist);
   getFromParent(root, x, &minDist);
   return minDist;
}
int main() {
   Node* root = getNode(4);
   root->left = getNode(2);
   root->right = getNode(-5);
   root->right->left = getNode(-2);
   root->right->right = getNode(6);
   Node *x = root->right;
   cout << "Closest distance of leaf from " << x->data <<" is: " << minimumDistance(root, x);
}

आउटपुट

Closest distance of leaf from -5 is: 1