1. find ceil node of BST.
O(longn)
/*
* 8
* 4 10
* 3 7 9 11
* 6
*/
public class CeilingNodeOfBST {
static class Node{
int val;
Node left;
Node right;
public Node(int v){
this.val = v;
left = null;
right = null;
}
}
public static int CeilUtil(Node root, int target, int min, int max){
if(target >= root.val){
if(root.right!=null){
return CeilUtil(root.right, target, root.val, max);
}else{
return max;
}
}else{
//target < root.val now.
if(root.left!=null){
return CeilUtil(root.left, target, min, root.val);
}else{
return root.val;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = new Node(8);
root.left = new Node(4);
root.right = new Node(10);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.right.left = new Node(9);
root.right.right = new Node(11);
root.left.right.left = new Node(6);
int res = CeilUtil(root, -1, Integer.MIN_VALUE, Integer.MAX_VALUE);
if(res==Integer.MAX_VALUE){
res = -1;
}
System.out.println(res);
return;
}
}
2. Only modify in find ceiling node util function, can find floor node of BST:
O(logn)
public class FloorNodeOfBST {
static class Node{
int val;
Node left;
Node right;
public Node(int v){
this.val = v;
left = null;
right = null;
}
}
public static int FloorUtil(Node root, int target, int min, int max){
if(target <= root.val){
if(root.left!=null){
return FloorUtil(root.left, target, min, root.val);
}else{
return min;
}
}else{
//target > root.val now.
if(root.right!=null){
return FloorUtil(root.right, target, root.val, max);
}else{
return root.val;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = new Node(8);
root.left = new Node(4);
root.right = new Node(10);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.right.left = new Node(9);
root.right.right = new Node(11);
root.left.right.left = new Node(6);
int res = FloorUtil(root, 4, Integer.MIN_VALUE, Integer.MAX_VALUE);
if(res==Integer.MIN_VALUE){
res = -1;
}
System.out.println(res);
return;
}
}
No comments:
Post a Comment