इस समस्या में हमें एक बाइनरी ट्री और पैरेंट पॉइंटर्स दिए जाते हैं। हमारा काम पैरेंट पॉइंटर्स वाले बाइनरी ट्री के राइट सिबलिंग को ढूंढना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
Node = 3
आउटपुट
7
समाधान दृष्टिकोण
समस्या का एक सरल समाधान निकटतम पूर्वज का लीफ नोड (जो न तो वर्तमान नोड है और न ही वर्तमान नोड का पैरेस्ट है) का पता लगाना है जो वर्तमान नोड के समान स्तर पर है। यह ऊपर जाते समय स्तरों की गिनती करके और फिर नीचे आते समय उन्हें नीचे गिनकर किया जाता है। और फिर नोड ढूँढना।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right, *parent;
};
Node* newNode(int item, Node* parent) {
Node* temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
temp->parent = parent;
return temp;
}
Node* findRightSiblingNodeBT(Node* node, int level) {
if (node == NULL || node->parent == NULL)
return NULL;
while (node->parent->right == node ||
(node->parent->right == NULL && node->parent->left == node)) {
if (node->parent == NULL || node->parent->parent == NULL)
return NULL;
node = node->parent;
level++;
}
node = node->parent->right;
if (node == NULL)
return NULL;
while (level > 0) {
if (node->left != NULL)
node = node->left;
else if (node->right != NULL)
node = node->right;
else
break;
level--;
}
if (level == 0)
return node;
return findRightSiblingNodeBT(node, level);
}
int main(){
Node* root = newNode(4, NULL);
root->left = newNode(2, root);
root->right = newNode(5, root);
root->left->left = newNode(1, root->left);
root->left->left->left = newNode(9, root->left->left);
root->left->left->left->left = newNode(3, root->left->left->left);
root->right->right = newNode(8, root->right);
root->right->right->right = newNode(0, root->right->right);
root->right->right->right->right = newNode(7, root->right->right->right);
Node * currentNode = root->left->left->left->left;
cout<<"The current node is "<<currentNode->data<<endl;
Node* rightSibling = findRightSiblingNodeBT(currentNode, 0);
if (rightSibling)
cout<<"The right sibling of the current node is "<<rightSibling->data;
else
cout<<"No right siblings found!";
return 0;
} आउटपुट
The current node is 3 The right sibling of the current node is 7