forked from HarshCasper/NeoAlgo
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LevelOrderTraversal.cpp
116 lines (80 loc) · 1.79 KB
/
LevelOrderTraversal.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
/*
This program is about Traversing elements of a binary Tree in a Level Order way.Here we will enter the values for
the nodes of the tree.
It will simply print the elements of the tree level by level by simply storing the
addresses of the nodes in a queue and printing the node whose address is on the front
,and calling the same function for left and right subtree recursively and the process
is iterated untill queue doesn't gets emptied.
*/
#include <iostream>
#include<queue>
using namespace std;
// Basic Definition of node in a Binary Tree
struct child {
int data;
child*LeftPtr;
child*RightPtr;
child(int value) {
data = value;
LeftPtr = NULL;
RightPtr = NULL;
}
};
// Function to build tree Recursively
child * buildTree() {
int d;
cin >> d;
if (d == -1) {
return NULL;
}
child*root = new child(d);
root->LeftPtr = buildTree();
root->RightPtr = buildTree();
return root;
}
// Function for implementing level order traversal using Queue
void levelOrder(child * root) {
if (root == NULL)
return;
queue <child*> q;
q.push(root);
while (!q.empty()) {
child*t = q.front();
cout << t -> data << endl;
if (t->LeftPtr)
q.push(t->LeftPtr);
if (t->RightPtr)
q.push(t->RightPtr);
q.pop();
}
}
int main() {
cout << "Enter the values of nodes of the tree: " << endl;
child*root = buildTree();
cout << "Level Order Traversal for the following Tree will be:" << endl;
levelOrder(root);
return 0;
}
/*
Output:-
Enter the values of nodes of the tree:
3
4
6
-1
-1
7
-1
-1
5
-1
-1
Level Order Traversal for the following Tree will be:
3
4
5
6
7
Time Complexity:- O(n)
Space Complexity:- O(n)
*/