-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBSTOperations.java
More file actions
95 lines (85 loc) · 2.62 KB
/
Copy pathBSTOperations.java
File metadata and controls
95 lines (85 loc) · 2.62 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
import java.util.Stack;
public class BSTOperations {
public static int kthSmallest(BSTNode root, int k){
if(root!=null){
k = kthSmallest(root.left, k);
k--;
if(k == 0){
System.out.println(root.data);
}
k = kthSmallest(root.right, k);
}
return k;
}
public static void inorderTraversal(BSTNode root){
Stack<BSTNode> s = new Stack<BSTNode>();
s.push(root);
BSTNode node = root;
while(!s.isEmpty()){
if(node !=null){
s.push(node);
node=node.left;
}
else{
node=s.pop();
System.out.println(node.data);
node = node.right;
}
}
}
// public static int findCeiling(BSTNode root, BSTNode prev, int val){
// if(root !=null){
// if(root.data == val)
// return root.data;
// if(root.data < val){
// if(prev != null && prev.data >= val)
// return prev.data;
// else {
// return findCeiling(root.right, root, val);
// }
// }
// else if(root.data > val){
// if(root.left == null){
// return root.data;
// }
// return findCeiling(root.left, root, val);
// }
// }
// return -1;
// }
// public static int findFloor(BSTNode root, BSTNode prev, int val){
// if(root!=null){
// if(root.data == val)
// return root.data;
// else if(root.data > val){
// if(prev !=null && prev.data <= val){
// return prev.data;
// }
// return findFloor(root.left, root, val);
// }
// else{
// if(root.right == null)
// return root.data;
// return findFloor(root.right, root, val);
// }
// }
// else return -1;
// }
public static int Ceil(BSTNode node, int input) {
// Base case
if (node == null) {
return -1;
}
// We found equal key
if (node.data == input) {
return node.data;
}
// If root's key is smaller, ceil must be in right subtree
if (node.data < input) {
return Ceil(node.right, input);
}
// Else, either left subtree or root has the ceil value
int ceil = Ceil(node.left, input);
return (ceil >= input) ? ceil : node.data;
}
}