-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBTOperations.java
More file actions
76 lines (72 loc) · 2.63 KB
/
Copy pathBTOperations.java
File metadata and controls
76 lines (72 loc) · 2.63 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
public class BTOperations {
public void printDescendants(BSTNode root, int k){
if(root == null || k<0 )
return;
if(k==0)
System.out.println(root.data);
printDescendants(root.left,k-1);
printDescendants(root.right,k-1);
}
public void printNearestk(BSTNode root, int k, int val, BSTNode[] ancestors, int index){
if(root == null)
return;
BSTNode temp =null, prevNode=null;
if(root.data == val){
printDescendants(root, k);
prevNode = root;
for(int i = index-1;i>=0;i--){
temp = ancestors[i];
if(k-index+i == 0){
System.out.println(temp.data);
return;
}
if(prevNode == temp.left){
printDescendants(temp.right,k-index+i-1);
}
else{
printDescendants(temp.left,k-index+i-1);
}
prevNode = temp;
}
}
else{
ancestors[index]=root;
printNearestk(root.left,k,val,ancestors,index+1);
printNearestk(root.right,k,val,ancestors,index+1);
}
}
public int nearestLeafNode(BSTNode root, int val, BSTNode[] ancestors, int index){
if(root == null)
return Integer.MAX_VALUE;
BSTNode temp, prevNode=root;
int minDist,i;
if(root.data == val){
minDist = nearestDescendantLeaf(root);
for(i=index-1;i>=0;i--){
temp = ancestors[i];
if(temp.left == prevNode){
minDist = Math.min(minDist,index-i+1+nearestDescendantLeaf(temp.right));
}
else{
minDist = Math.min(minDist,index-i+1+nearestDescendantLeaf(temp.left));
}
prevNode = temp;
}
return minDist;
}
else{
ancestors[index]=root;
return Math.min(nearestLeafNode(root.left,val,ancestors,index+1),
nearestLeafNode(root.right,val,ancestors,index+1));
}
}
public int nearestDescendantLeaf(BSTNode root){
if(root == null) return Integer.MAX_VALUE;
if(root.left == null && root.right == null)
return 0;
// int left = nearestDescendantLeaf(root.left);
// int right = nearestDescendantLeaf(root.right);
// int ans = Math.min(nearestDescendantLeaf(root.left), nearestDescendantLeaf(root.right));
return 1+Math.min(nearestDescendantLeaf(root.left), nearestDescendantLeaf(root.right));
}
}