Sunday, April 17, 2016

Ceiling Node of BST + Floor Node of BST

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