এই সমস্যাতে, আমাদের একটি বাইনারি ট্রি এবং প্যারেন্ট পয়েন্টার দেওয়া আছে। আমাদের কাজ হলো প্যারেন্ট পয়েন্টার ব্যবহার করে বাইনারি ট্রিতে ডান সিবলিং (Right Sibling) বের করা।
উদাহরণ দিয়ে সমস্যা বোঝা যাক,
ইনপুট
Node = 3
আউটপুট
7
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হলো নিকটতম পূর্বপুরুষ (ancestor) এর ليف নোড (leaf node) বের করা যা বর্তমান নোড বা বর্তমান নোডের প্যারেন্ট নয় এবং যা বর্তমান নোডের মতো একই লেভেলে (level) আছে। এটি লেভেল কাউন্ট করলে উপরে যাওয়ার সময় এবং নিচে আসার সময় লেভেল কাউন্ট কমিয়ে করা হয়। এবং তারপর নোডটি বের করা হয়।
সমাধান কোড:
উদাহরণ
#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
