মনে করুন আমাদের একটি বাইনারি ট্রি এবং একটি মান K আছে। কাজটি হল ভার্টিকাল অর্ডার ট্রাভার্সালে K-তম নোড প্রিন্ট করা। যদি এমন কোনো নোড না থাকে, তবে -1 রিটার্ন করুন। তাই যদি ট্রিটি নিচের মতো হয় -
ভার্টিকাল অর্ডার ট্রাভার্সাল হল -
4 2 1 5 6 3 8 7 9
তাই যদি K = 3 হয়, তবে ফলাফল হবে 1।
অ্যাপ্রোচটি সহজ। আমরা ভার্টিকাল অর্ডার ট্রাভার্সাল করব, তারপর চেক করব বর্তমান নোডটি k-তম নোড কিনা, যদি হ্যাঁ, তবে রিটার্ন করব।
উদাহরণ
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node* getNode(int key) {
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return node;
}
int findKthNodeVertical(Node* root, int k) {
if (!root || k == 0)
return -1;
int n = 0;
int k_node = -1;
map<int, vector<int> > current_map;
int hd = 0;
queue<pair<Node*, int> > que;
que.push(make_pair(root, hd));
while (!que.empty()) {
pair<Node*, int> temp = que.front();
que.pop();
hd = temp.second;
Node* node = temp.first;
current_map[hd].push_back(node->key);
if (node->left != NULL)
que.push(make_pair(node->left, hd - 1));
if (node->right != NULL)
que.push(make_pair(node->right, hd + 1));
}
map<int, vector<int> >::iterator it;
for (it = current_map.begin(); it != current_map.end(); it++) {
for (int i = 0; i < it->second.size(); ++i) {
n++;
if (n == k)
return (it->second[i]);
}
}
if (k_node == -1)
return -1;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
root->right->left->right = getNode(8);
root->right->right->right = getNode(9);
int k = 3;
cout << "Kth node in vertical traversal: " << findKthNodeVertical(root, k);
}
আউটপুট
Kth node in vertical traversal: 1
