PracticeCodes/connect_nodes_level.cpp at master · shriyaEsha/PracticeCodes · 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
#include<iostream>
#include<queue>
using namespace std;

struct node{
int data;
node *left,*right,*nr;
};

node * create(int d)
{
node * t = new node;
t->data = d;
t->left = t->right = t->nr = NULL;
return t;
}

void level_order(node *root)
{
char ch;
queue<node*>q;
q.push(root);
node *nullnode = create(-1);
q.push(nullnode);

while(q.size()>1)
{
node * elem = q.front();
q.pop();
if(q.size()>0)
if(q.front() == nullnode)
{
elem->nr = NULL;
q.pop();
}
else
elem->nr = q.front();

if(elem->left)
q.push(elem->left);
if(elem->right)
q.push(elem->right);
q.push(nullnode);
}
}

int max(int a,int b)
{
return a>b?a:b;
}

int height(node *root)
{
if(!root)return 0;
return 1+max(height(root->left),height(root->right));
}


void disp_level(node *root,int level)
{
if(!root)return;
if(level==1)
cout<<root->data<<" ";
disp_level(root->left,level-1);
disp_level(root->right,level-1);
}

void disp_level_nr(node *root,int level)
{
if(!root)return;
if(level==1)
{
node * cur = root;
do
{cout<<root->data<<"-->";
if(cur->nr)
cur = cur->nr;
}while(cur->nr);
}
disp_level_nr(root->left,level-1);
disp_level_nr(root->right,level-1);
}

void disp(node *root)
{
int h = height(root)+1;
for(int i=1;i<=h;i++)
{
disp_level(root,i);
cout<<endl;
}
cout<<endl;
for(int i=1;i<=h;i++)
{
disp_level_nr(root,i);
cout<<endl;
}


}

main()
{
node *root = NULL;
root = create(12);
root->left = create(9);
root->right = create(30);
root->left->left = create(8);
root->left->right = create(10);
root->right->right = create(35);

disp(root);
level_order(root);
}