Daily Archives: December 24, 2014

Problem description:
Given a Binary Tree and a key ‘k’, find distance of the closest leaf from ‘k’.

              A
            /    \    
           B       C
                 /   \  
                E     F   
               /       \
              G         H
             / \       /
            I   J     K
Closest key to 'H' is 'K', so distance is 1 for 'H'
Closest key to 'C' is 'B', so distance is 2 for 'C'
Closest key to 'E' is either 'I' or 'J', so distance is 2 for 'E' 
Closest key to 'B' is 'B' itself, so distance is 0 for 'B'

Solution:
Find all the ancestry of the target node, and the min-depth of them. Distance from target to its ancestry, plus distance from ancestry to ancestry’s min-depth leaf is a potential result. Among them and the min-depth of the target node itself, find the smallest one.

The traversal process is:
For each node, it traverse the left and right sub-tree, and get the min-depth from each sub-tree. And it will return min-depth to its ancestry.
After traverse each sub-tree, if it found the target in either sub-tree, this node is treated as an ancestry of the target node. And the ancestry information should be stored.

In my code, I define a AncestryInfo class, to restore the ancestry information:
class AncestryInfo{
int[] ancestry_record;    //records the ancestry nodes from target node. Target node is also included in position 0;
int[] ancestry_level;    //records the min deep of ancestry nodes.
int[] leaf;        //records the leaf which the ancestry nodes reach to the min deep
}

1. public class FindNearestLeaf {
3.     public static void main(String[] args) {
4.         Tree tree = Tree.getTree();
5.         findNearestLeaf(tree, 7);
6.         System.out.println();
7.     }
9.     public static void findNearestLeaf(Tree tree, int value){
10.         AncestryInfo ancestry = new AncestryInfo();
11.         //traverse the tree, to find the relative information
12.         findNearestLeafUtil(tree, value, ancestry, new MyInteger(), new MyInteger(), new MyBoolean());
13.         int leaf = ancestry.leaf[0];
14.         int distance = ancestry.ancestry_level[0];
15.         for(int i=1;i
16.             if(i-0+ancestry.ancestry_level[i]
17.                 distance = i-0+ancestry.ancestry_level[i];
18.                 leaf = ancestry.leaf[i];
19.             }
20.         }
21.         distance–;
22.         System.out.println(“Nearest Leaf:” + leaf + “\tDistance:” + distance);
23.     }
25.     public static void findNearestLeafUtil(Tree root, int value, AncestryInfo anc, MyInteger depth, MyInteger leaf, MyBoolean found){
26.         if(root==null){
27.             return;
28.         }
29.         MyInteger l_depth = new MyInteger(Integer.MAX_VALUE);
30.         MyInteger r_depth = new MyInteger(Integer.MAX_VALUE);
31.         MyBoolean l_found = new MyBoolean();
32.         MyBoolean r_found = new MyBoolean();
33.         MyInteger l_leaf = new MyInteger();
34.         MyInteger r_leaf = new MyInteger();
35.         if(root.left!=null){
36.             findNearestLeafUtil(root.left, value, anc, l_depth, l_leaf, l_found);
37.         }
38.         if(root.right!=null){
39.             findNearestLeafUtil(root.right, value, anc, r_depth, r_leaf, r_found);
40.         }
41.         if(root.left==null&&root.right==null){    // current node is a leaf
42.             depth.i = 1;
43.             leaf.i = root.value;
44.         }
45.         else{    //if current node is not a leaf, get the depth from information of 2 sub tress.
46.             depth.i = Math.min(l_depth.i, r_depth.i) + 1;
47.             leaf.i = l_depth.i
48.         }
49.         found.bool = l_found.bool||r_found.bool;
50.         if(found.bool){
51.             //if the target node is already found, then current node is treated as an ancestry. So store the ancestry information.
52.             anc.ancestry_record = Arrays.copyOf(anc.ancestry_record, anc.ancestry_record.length+1);
53.             anc.ancestry_record[anc.ancestry_record.length-1] = root.value;
54.             anc.ancestry_level = Arrays.copyOf(anc.ancestry_level, anc.ancestry_level.length+1);
55.             anc.ancestry_level[anc.ancestry_level.length-1] = depth.i;
56.             anc.leaf = Arrays.copyOf(anc.leaf, anc.leaf.length+1);
57.             anc.leaf[anc.leaf.length-1] = leaf.i;
58.             return;
59.         }
60.         if(root.value==value){    //current node is the target, initial the ancestry information
61.             found.bool = true;
62.             anc.ancestry_record = new int[]{root.value};
63.             anc.ancestry_level = new int[]{depth.i};
64.             anc.leaf = new int[]{leaf.i};
65.             return;
66.         }
67.         return;
68.     }
69. }
71. class AncestryInfo{
72.     int[] ancestry_record;    //records the ancestry nodes from target node. Target node is also included in position 0;
73.     int[] ancestry_level;    //records the min deep of ancestry nodes.
74.     int[] leaf;        //records the leaf which the ancestry nodes reach to the min deep
75. }
76. class MyBoolean {
77.     public boolean bool;
78.     public MyBoolean(boolean bool){
79.         this.bool = bool;
80.     }
81.     public MyBoolean(){
82.         this.bool = false;
83.     }
84.     public String toString(){
85.         return String.valueOf(bool);
86.     }
87. }
89. class MyInteger{
90.     public int i = 0;
91.     public MyInteger(int i){
92.         this.i = i;
93.     }
94.     public MyInteger(){}
96.     public String toString(){
97.         return String.valueOf(i);
98.     }
99. }
101. class Tree{
102.     public Tree(int value){
103.         this.value = value;
104.     }
105.     public Tree(String value){
106.         this.valueString = value;
107.     }
108.     public Tree left;
109.     public Tree right;
110.     public int value;
111.     public String valueString;
112.     public static Tree getTree(){
113.         Tree t18 = new Tree(18);
114.         Tree t17 = new Tree(17);
115.         Tree t16 = new Tree(16);
116.         Tree t15 = new Tree(15);
117.         Tree t14 = new Tree(14);
118.         Tree t13 = new Tree(13);
119.         Tree t12 = new Tree(12);
120.         Tree t11 = new Tree(11);
121.         Tree t10 = new Tree(10);
122.         Tree t9 = new Tree(9);
123.         Tree t8 = new Tree(8);
124.         Tree t7 = new Tree(7);
125.         Tree t6 = new Tree(6);
126.         Tree t5 = new Tree(5);
127.         Tree t4 = new Tree(4);
128.         Tree t3 = new Tree(3);
129.         Tree t2 = new Tree(2);
130.         Tree t1 = new Tree(1);
131.         t8.left = t9;
132.         t6.left = t8;
133.         t5.right = t7;
134.         t4.left = t5;
135.         t4.right = t6;
136.         t2.left = t4;
137.         t1.left = t2;
138.         t1.right = t3;
139.         t6.right = t10;
140.         t3.left = t11;
141.         t3.right = t12;
142.         t12.left = t13;
143.         t12.right = t14;
144.         t13.left = t15;
145.         t13.right = t16;
146.         t16.right = t17;
147.         t17.right = t18;
148.         return t1;
149.     }
150. }