Friday, February 27, 2015

floor and ceiling of a Binary Search Tree

Binary search tree elements can be printed in sorted order, if we traverse the tree in InOrder way.

Floor:
Floor of an element in a tree is:
1. if any element exists with the same value, then that value is floor
2. If the element lies between any two adjacent elements in tree, then the lowest valued element is the floor.
3. If its less than the lowest element in the tree, then the floor is "0"

Ceiling:
Ceil of an element in a tree is:
1. If any element exists with the same value, then that value is the ceil
2. If the lies between any two adjacent elements in tree, then the highest valued element is the ceil.
3. If its greater than the highest element in tree, then the ceil is "0".

Program:

class FloorCeiling {
        static int ceil(TreeNode root, int data) {
                if(root == null)
                        return 0;

                if(data == root.getData())
                        return root.getData();
                else if(data > root.getData())
                        return ceil(root.getRight(), data);
                else {
                        int data1 = ceil(root.getLeft(), data);

                        if(data1 != 0)
                                return data1;
                        else
                                return root.getData();
                }
        }

        static int floor(TreeNode root, int data) {
                if(root == null)
                        return 0;

                if(data == root.getData())
                        return root.getData();
                else if(data < root.getData())
                        return floor(root.getLeft(), data);
                else {
                        int data1 = floor(root.getRight(), data);

                        if(data1 != 0)
                                return data1;
                        else
                                return root.getData();
                }
        }

        static public void main(String[] args) {
                TreeNode root = TreeUtil.getBinaryTree();

                Traversal.inOrderTrav(root);
                System.out.println();

                System.out.println("3: " + floor(root, 1));
        }
}

No comments:

Post a Comment