-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbinary_tree.cpp
127 lines (119 loc) · 2.72 KB
/
binary_tree.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
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std ;
class Node
{
public:
int data;
Node *left,*right;
Node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
//void printGivenLevel(node* root, int level);
int height(node* node);
//node* newNode(int data);
void printLevel(Node *root,int h)
{
if(root==NULL) return ;
if(h==1)
{
cout<<root->data<<endl;
else if(h>1)
{
print(root->left,h-1);
printLevel(root->right,h-1);
}
}
void printLevelByLevel(Node *root)
{
int h = height(root);
for(int i = 1;i<=h;i++)
{
printLevel(root,i);
}
}
void printPostorder(Node *root)
{
if(root==NULL) return ;
printPostorder(root->left);
printPostorder(root->right);
cout<<root->data<<" ";
}
void printInorder(Node *root)
{
if(root==NULL) return ;
printInorder(root->left);
cout<<root->data<<" ";
printInorder(root->right);
}
int getMax(Node *root)
{
if(root==NULL) return INT_MIN;
int k= getMax(root->left);
int l = getMax(root->right);
int j = max(max(k,l),root->data);
return j;
}
int height(Node *root)
{
if(root == NULL) return 0;
int k = height(root->left);
int l = height(root->right);
int l1 = max(k,l)+1;
return l1;
}
static Node * const DELIMITER = nullptr;
void printLevelByLevel(Node *root) {
if (root == nullptr) return;
queue<Node *> qu;
qu.push(root);
qu.push(DELIMITER);
while (true) {
Node *curr = qu.front();
qu.pop();
if (curr != DELIMITER) {
cout << curr->data << ' ';
if (curr->left != nullptr) {
qu.push(curr->left);
}
if (curr->right != nullptr) {
qu.push(curr->right);
}
}
else {
cout << '\n';
if (qu.empty()) break;
qu.push(DELIMITER);
}
}
}
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);
printLevelByLevel(root);
cout<<endl;
cout<<"Max in tree is :"<<getMax(root)<<endl;
cout<<"Height of the tree is "<<height(root)<<endl;
cout<<"Inorder of tree is :";
printInorder(root);
cout<<endl;
cout<<"Post order of tree is :";
printPostorder(root);
printLevelByLevel(root);
}