Repository navigation
Expand file tree
/
Copy pathDiameter.java
More file actions
154 lines (131 loc) · 3.78 KB
/
Copy pathDiameter.java
File metadata and controls
154 lines (131 loc) · 3.78 KB
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
package binaryTrees;
class Height
{
int h;
}
/* Class to print the Diameter */
public class Diameter
{
Node root;
/* define height =0 globally and call diameterOpt(root,height)
from main */
int diameterOpt(Node root, Height height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
Height lh = new Height(), rh = new Height();
if (root == null)
{
height.h = 0;
return 0; /* diameter is also 0 */
}
/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
lh.h++; rh.h++;
int ldiameter = diameterOpt(root.left, lh);
int rdiameter = diameterOpt(root.right, rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
height.h = Math.max(lh.h, rh.h) + 1;
return Math.max(lh.h + rh.h + 1, Math.max(ldiameter, rdiameter));
}
/* A wrapper over diameter(Node root) */
int diameter()
{
Height height = new Height();
return diameterOpt(root, height);
}
/*The function Compute the "height" of a tree. Height is the
number f nodes along the longest path from the root node
down to the farthest leaf node.*/
static int height(Node node)
{
/* base case tree is empty */
if (node == null)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return (1 + Math.max(height(node.left), height(node.right)));
}
/*
// INORDER ITERATIVE
while(!s.isEmpty()){
node = s.pop();
if(!visited(node) and node.left != null){
while(node.left != null){
s.push(node.left);
}
} else {
visit(node);
if(node.right != null){
s.push(node.right);
}
}
}
while(!done){
if( current!= null ){
s.push(current.left);
current = current.left;
}else{
if(!s.isEmpty()){
current = s.pop();
visit(current);
current = current.right;
}else{
done = true;
}
}
}
// POST ORDER TRAVERSAL
void postOrder(Node root){
if(root == null)
return null;
while(!s.isEmpty()){
while(root!=null){
if(root.right != null){
s.push(root.right);
}
s.push(root)
root = root.left;
}
node = s.pop();
if(node.right != null && node.right == s.peek()){
right = s.pop();
s.push(node);
root = right;
}else{
visit(node);
}
}
// PRINT ANCESTOR USING POST ORDER TRAVERSAL ITERATIVE
while (1) {
while (root && root->data != key) {
s.push(root); // push current node
root = root->left; // move to next node
}
if (root && root->data == key)
break;
if (s.peek()->right == NULL) {
root = s.pop();
while (!s.isEmpty() && peek(stack)->right == root){
root = s.pop();
}
}
root = isEmpty(stack)? NULL: peek(stack)->right;
}
*/
public static void main(String args[])
{
/* creating a binary tree and entering the nodes */
Diameter tree = new Diameter();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("The diameter of given binary tree is : "
+ tree.diameter());
}
}