बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल

यहां हम एक दिलचस्प समस्या देखेंगे। हमारे पास एक बाइनरी ट्री है। हमें ट्री को एंटी-क्लॉकवाइज तरीके से ट्रैवर्स करना है। ट्रैवर्सल इस प्रकार होगा:

ट्रैवर्सल अनुक्रम है: 1, 8, 9, 10, 11, 12, 13, 14, 15, 3, 2, 4, 5, 6, 7

एल्गोरिदम

antiClockTraverse(root)

शुरुआत
    i := 1, j := ट्री की ऊंचाई
    flag := false
    जबकि i <= j, करें
        यदि flag गलत है, तो
            लेवल i के लिए ट्री एलिमेंट्स को दाएं से बाएं प्रिंट करें
            flag := true
            i := i + 1
        अन्यथा
            लेवल j के लिए ट्री एलिमेंट्स को बाएं से दाएं प्रिंट करें
            flag := false
            j := j - 1
        यदि समाप्त
    पूर्ण
समाप्त

उदाहरण

#include <iostream>
using namespace std;

class Node {
public:
    Node* left;
    Node* right;
    int data;
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int getHeight(Node* root) {
    if (root == NULL) return 0;
    int hl = getHeight(root->left);
    int hr = getHeight(root->right);
    return 1 + max(hl, hr);
}

void printLeftToRight(Node* root, int level) {
    if (root == NULL) return;
    if (level == 1) cout << root->data << " ";
    else if (level > 1) {
        printLeftToRight(root->left, level - 1);
        printLeftToRight(root->right, level - 1);
    }
}

void printRightToLeft(Node* root, int level) {
    if (root == NULL) return;
    if (level == 1) cout << root->data << " ";
    else if (level > 1) {
        printRightToLeft(root->right, level - 1);
        printRightToLeft(root->left, level - 1);
    }
}

void antiClockTraverse(Node* root) {
    int i = 1;
    int j = getHeight(root);
    int flag = 0;
    while (i <= j) {
        if (flag == 0) {
            printRightToLeft(root, i);
            flag = 1;
            i++;
        } else {
            printLeftToRight(root, j);
            flag = 0;
            j--;
        }
    }
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->left->left->left = new Node(8);
    root->left->left->right = new Node(9);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(11);
    root->right->left->left = new Node(12);
    root->right->left->right = new Node(13);
    root->right->right->left = new Node(14);
    root->right->right->right = new Node(15);
    antiClockTraverse(root);
    return 0;
}

आउटपुट

1 8 9 10 11 12 13 14 15 3 2 4 5 6 7