অ্যান্টি-ক্লকওয়াইজ স্পাইরাল ট্রাভার্সাল মানে বাইনারি ট্রি লেভেল-ভিত্তিক স্পাইরাল আকারে ট্রাভার্স করা, কিন্তু উল্টা দিকে (Anti-clockwise)।
অ্যালগরিদম
i = 1(রুট লেভেল),j = height(root)।flagব্যবহার করে বাম-ডান আলটারনেট করুন।flag=0হলে ডান-से-বাম,flag=1হলে বাম-से-ডান প্রিন্ট করুন।- প্রতিটি ইটারেশনে
i++বাj--করুন।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node {
Node *left, *right;
int data;
Node(int d) : data(d), left(NULL), right(NULL) {}
};
int height(Node* root) {
if (!root) return 0;
return 1 + max(height(root->left), height(root->right));
}
void leftToRight(Node* root, int level) {
if (!root) return;
if (level == 1) cout << root->data << " ";
else {
leftToRight(root->left, level-1);
leftToRight(root->right, level-1);
}
}
void rightToLeft(Node* root, int level) {
if (!root) return;
if (level == 1) cout << root->data << " ";
else {
rightToLeft(root->right, level-1);
rightToLeft(root->left, level-1);
}
}
int main() {
Node* root = new Node(1);
root->left = new Node(2); root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5); root->right->right = new Node(7);
root->left->left->left = new Node(10); root->left->left->right = new Node(11);
root->right->right->left = new Node(8);
int i = 1, j = height(root), flag = 0;
while (i <= j) {
if (flag == 0) { rightToLeft(root, i); flag = 1; i++; }
else { leftToRight(root, j); flag = 0; j--; }
}
return 0;
}
আউটপুট
1 10 11 8 3 2 4 5 7
