-
Notifications
You must be signed in to change notification settings - Fork 3
/
zigZagTraversal.cpp
119 lines (102 loc) · 2.11 KB
/
zigZagTraversal.cpp
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
/*
* Print a level order zig-zag traversal.
*
*/
#include<iostream>
template <typename T>
struct Node {
T data;
Node *left;
Node *right;
};
template <typename T>
Node<T> * newNode( T data )
{
Node<T> * temp = new Node<T>;
temp->data = data;
temp->left = temp->right = nullptr;
return temp;
}
template <typename T>
void insert( Node<T>* & node, T data)
{
if ( node == nullptr )
{
node = newNode( data );
}
else
{
if ( data < node->data )
{
insert( node->left, data );
}
else
{
insert( node->right, data);
}
}
}
template <typename T>
void printLevel( Node<T> * node, int level, bool zig )
{
if ( node == nullptr ) {
return;
}
if ( level == 1 ) {
std::cout << node->data << " ";
}
else {
if( zig ){
printLevel( node->left, level - 1, zig );
printLevel( node->right, level - 1, zig );
} else {
printLevel( node->right, level - 1, zig );
printLevel( node->left, level - 1, zig );
}
}
}
template <typename T>
int height ( Node<T> * node )
{
if ( node == nullptr ) {
return 0;
}
int lheight = height( node->left );
int rheight = height( node->right );
return ( 1 + (( lheight > rheight ) ? lheight : rheight));
}
template <typename T>
void levelOrderTraversal( Node<T> *root )
{
int h = height(root);
bool zig = true;
for ( int i = 1; i <= h; ++i ) {
printLevel( root, i, zig );
std::cout << std::endl;
zig = !zig;
}
}
template <typename T>
void inorder( Node<T> * node )
{
if ( node != nullptr ) {
inorder( node->left );
std::cout << node->data << " " ;
inorder( node->right );
}
}
int main()
{
Node<int> *root;
insert( root, 11 );
insert( root, 9 );
insert( root, 20 );
insert( root, 15 );
insert( root, 25 );
std::cout << "Inorder:";
inorder(root);
std::cout << std::endl;
std::cout << "Level order: \n";
levelOrderTraversal( root );
return 0;
}