-
Notifications
You must be signed in to change notification settings - Fork 10
/
Copy pathDiagonal Traversal of Binary Tree
106 lines (101 loc) · 2.64 KB
/
Diagonal Traversal of Binary Tree
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
import java.util.ArrayList;
import java.util.List;
class node{
int data;
node left;
node right;
node(int data){
this.data=data;
left=null;
right=null;
}
}
class queue{
List<custom> queue=new ArrayList<custom>();
void add(node n,int pos){
custom c=new custom(n,pos);
queue.add(c);
}
custom pop(){
return queue.remove(0);
}
boolean isEmpty(){
return queue.isEmpty();
}
}
class custom{
node n;
int pos;
custom(node n,int pos){
this.n=n;
this.pos=pos;
}
}
class tree{
node root;
void diagonalTraversal(){
queue q=new queue();
q.add(root,0);
q.add(null,0);
int current=0;
List<ArrayList<custom>>list=new ArrayList<ArrayList<custom>>();
list.add(new ArrayList<custom>());
while(!q.isEmpty()){
custom n=q.pop();
if(n.n==null){
current++;
list.add(new ArrayList<custom>());
q.add(null,0);
if(q.queue.size()==1&&q.queue.get(0).n==null){
q.pop();
}
}
else{
// System.out.println(n.n.data);
list.get(current).add(n);
if(n.n.left!=null){
q.add(n.n.left,n.pos-1);
}
if(n.n.right!=null){
q.add(n.n.right,n.pos+1);
}
}
}
int count=0;
for(int i=0;i<list.size();i++){
int ind=count;
count--;
for(int j=i;j<list.size();j++){
List <custom>l=list.get(j);
int cc=0;
for(int k=0;k<l.size();k++){
custom f=l.get(k);
if(f.pos==ind){
cc++;
System.out.print(f.n.data+",");
if(cc==2){
break;
}
}
}
ind++;
}
System.out.println();
}
}
}
public class Implementation {
public static void main(String []args){
tree tree=new tree();
tree.root=new node(8);
tree.root.left = new node(3);
tree.root.right = new node(10);
tree.root.left.left = new node(1);
tree.root.left.right = new node(6);
tree.root.right.right = new node(14);
tree.root.right.right.left = new node(13);
tree.root.left.right.left = new node(4);
tree.root.left.right.right = new node(7);
tree.diagonalTraversal();
}
}