इस समस्या में हमें एक बाइनरी ट्री और पैरेंट पॉइंटर्स दिए गए हैं। हमारा कार्य पैरेंट पॉइंटर्स के साथ बाइनरी ट्री में दायां सहोदर खोजना है।
आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
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
