Open-Source/binaryzigzag.cpp at main · Ayushsinhahaha/Open-Source · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>

#include <stack>

using namespace std;

struct Node {

    int data;

    struct Node *left, *right;

};

void zizagtraversal(struct Node* root)

{

    if (!root)

        return;

    stack<struct Node*> currentlevel;

    stack<struct Node*> nextlevel;

    currentlevel.push(root);

    bool lefttoright = true;

    while (!currentlevel.empty()) {


        struct Node* temp = currentlevel.top();

        currentlevel.pop();

        if (temp) {

            cout << temp->data << " ";

            if (lefttoright) {

                if (temp->left)

                    nextlevel.push(temp->left);

                if (temp->right)

                    nextlevel.push(temp->right);

            }

            else {

                if (temp->right)

                    nextlevel.push(temp->right);

                if (temp->left)

                    nextlevel.push(temp->left);

            }

        }


        if (currentlevel.empty()) {

            lefttoright = !lefttoright;

            swap(currentlevel, nextlevel);

        }

    }

}

struct Node* newNode(int data)

{

    struct Node* node = new struct Node;

    node->data = data;

    node->left = node->right = NULL;

    return (node);

}

int main()

{

    struct Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(7);

    root->left->right = newNode(6);

    root->right->left = newNode(5);

    root->right->right = newNode(4);

    cout << "ZigZag Order traversal of binary tree is \n";


    zizagtraversal(root);


    return 0;

}