Algorithm-and-Data-Structure/AlgorithmCode/DiameterOfTree.java at master · lemidia/Algorithm-and-Data-Structure · 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
publicclassDiameterOfTree {

staticclassTreeNode {
intindex;
TreeNodechildren[];

publicTreeNode(intindex) {
this.index = index;
children = newTreeNode[2];
 }
 }

/*
 Sample Tree used in this code.

 0
 / \
 / \
 1 2
 / \
 / \
 3 4

 */

publicstaticintdiameterOfTree (TreeNoderoot) {
if (root == null)
return0;
// Diameter of the tree is
// root diameter which is 1 + left sub tree height + right sub tree height

returnheightOfSubTree(root.children[0], 1)
 + heightOfSubTree(root.children[1], 1) + 1;
 }

publicstaticintheightOfSubTree (TreeNodeat, intdiameter) {
if (at == null)
return0;

intleft = heightOfSubTree(at.children[0], diameter + 1);
intright = heightOfSubTree(at.children[1], diameter + 1);

if (left == 0 && right == 0)
returndiameter;

returnMath.max(left, right);
 }

publicstaticvoidmain(String[] args) {
// Construct Sample Tree
TreeNoderoot = newTreeNode(0);
root.children[0] = newTreeNode(1);
root.children[1] = newTreeNode(2);
root.children[0].children[0] = newTreeNode(3);
root.children[0].children[1] = newTreeNode(4);

intdiameter = diameterOfTree(root);
System.out.println("Diameter of the tree is : " + diameter);

// Output:
// Diameter of the tree is : 4
 }
}