Daily Archives: January 7, 2015

This is a practice for tree function. It returns the diameter trail of a tree by traversing each node only one time.
The process is similar to finding diameter. During traverse each node, keep track of the trail of from the furthest leaf to node itself.
For the following tree, it should return the diameter trail 1, 2, 3, 4, 5, 6

Code:

1. import java.util.ArrayList;
2. import java.util.Iterator;
3. public class FindDiameterTrail{
5.     public static void main(String[] args) {
6.         Tree t = Tree.getTree();
7.         findDiameterTrail(t);
8.     }
10.     public static void findDiameterTrail(Tree t){
11.         DiaData diaData = getDiameterUtil(t);
12.         ArrayList result = diaData.leftTrail;
13.         while(!result.isEmpty()){
14.             Tree tree = result.remove(0);
15.             System.out.println(tree.value);
16.         }
17.         System.out.println(diaData.lca.value);
18.         result = diaData.rightTrail;
19.         while(!result.isEmpty()){
20.             Tree tree = result.remove(result.size()-1);
21.             System.out.println(tree.value);
22.         }
23.     }
25.     public static DiaData getDiameterUtil(Tree t){
26.         if(t==null){
27.             DiaData diameter = new DiaData(0, 0);
28.             diameter.leafTrail = new ArrayList();
29.             diameter.leftTrail = new ArrayList();
30.             diameter.rightTrail = new ArrayList();
31.             return diameter;
32.         }
33.         DiaData left = getDiameterUtil(t.left);
34.         DiaData right = getDiameterUtil(t.right);
35.         DiaData diameter = new DiaData();
36.         //deal with the depth
37.         if(left.depth>right.depth){
38.             diameter.depth = left.depth + 1;
39.             diameter.leafTrail = trailCopy(left.leafTrail);
40.         }
41.         else{
42.             diameter.depth = right.depth + 1;
43.             diameter.leafTrail = trailCopy(right.leafTrail);
44.         }
45.         diameter.leafTrail.add(t);
46.         //deal with the diameter node.
47.         if(left.depth+right.depth+1>Math.max(left.diameter, right.diameter)){
48.             diameter.diameter = left.depth+right.depth+1;
49.             diameter.leftTrail = left.leafTrail;
50.             diameter.rightTrail = right.leafTrail;
51.             diameter.lca = t;
52.             return diameter;
53.         }
54.         if(left.diameter>right.diameter){
55.             diameter.leftTrail = left.leftTrail;
56.             diameter.rightTrail = left.rightTrail;
57.             diameter.diameter = left.diameter;
58.             diameter.lca = left.lca;
59.         }
60.         else{
61.             diameter.leftTrail = right.leftTrail;
62.             diameter.rightTrail = right.rightTrail;
63.             diameter.diameter = right.diameter;
64.             diameter.lca = right.lca;
65.         }
66.         return diameter;
67.     }
69.     public static ArrayList trailCopy(ArrayList t){
70.         ArrayList result = new ArrayList();
71.         if(t==null||t.isEmpty()){
72.             return result;
73.         }
74.         Iterator itr = t.iterator();
75.         while(itr.hasNext()){
76.             result.add(itr.next());
77.         }
78.         return result;
79.     }
80. }
81. class DiaData{
82.     int depth;
83.     int diameter;
84.     ArrayList leftTrail;
85.     ArrayList rightTrail;
86.     Tree lca;
87.     ArrayList leafTrail;
88.     public DiaData(int depth, int diameter){
89.         this.depth = depth;
90.         this.diameter = diameter;
91.     }
92.     public DiaData(){}
93. }
94. class Tree{
95.     public Tree(int value){
96.         this.value = value;
97.     }
98.     public Tree(String value){
99.         this.valueString = value;
100.     }
101.     public Tree left;
102.     public Tree right;
103.     public int value;
104.     public String valueString;
106.     public static Tree getTree(){
107.         Tree t1 = new Tree(1);
108.         Tree t2 = new Tree(2);
109.         Tree t3 = new Tree(3);
110.         Tree t4 = new Tree(4);
111.         Tree t5 = new Tree(5);
112.         Tree t6 = new Tree(6);
113.         Tree t7 = new Tree(7);
114.         Tree t8 = new Tree(8);
115.         t7.left = t4; t7.right = t8;
116.         t4.left = t3; t4.right = t5;
117.         t3.left = t2;
118.         t2.right = t1;
119.         t5.right = t6;
120.         return t7;
121.     }
122. }