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));
        }

}

Sorting a queue with the help of another queue

class Queue {
        int capacity = -1, front = -1, rear = -1;
        int[] queue = null;

        Queue(int size) {
                capacity = size;

                queue = new int[size];
        }

        boolean isEmpty() {
                return front == -1;
        }

        boolean isFull() {
                return  (rear+1)%capacity == front;
        }

        int getSize() {
                return (front>rear) ? (capacity - front + rear + 1) : ( (front == -1) ? 0 : rear - front + 1 ) ;
        }

        int peek() {
                if(isEmpty()) {
                        System.out.println("Queue is empty");

                        return -1;
                }

                return queue[front];
        }

        void enQueue(int data) {
                if(isFull()) {
                        System.out.println("Queue is full");

                        return;
                }

                rear = (rear+1)%capacity;

                if(front == -1)
                        front = rear;

                queue[rear] = data;
        }

        int deQueue() {
                if(isEmpty()) {
                        System.out.println("Queue is already empty");

                        return -1;
                }

                int data = queue[front];

                if(front == rear)
                        front = rear = -1;
                else
                        front = (front+1)%capacity;

                return data;
        }

        void print() {
                int tempFront = front;

                if(tempFront == -1) {
                        System.out.println("Queue is empty.");

                        return;
                }

                while(tempFront != rear) {
                        System.out.print(queue[tempFront] + ", ");
                        tempFront = (tempFront+1)%capacity;
                }

                System.out.println(queue[tempFront]);
        }
}





class SortQueue {
        static public void sortQueue(Queue q) {
                if(q.isEmpty())
                        return;

                Queue tempQ = new Queue(q.getSize());

                int qData = q.deQueue();

                tempQ.enQueue(qData);

                while(q.getSize() != 0) {
                        qData = q.peek();

                        while(tempQ.getSize() != 0 && qData < tempQ.peek())
                                q.enQueue(tempQ.deQueue());

                        tempQ.enQueue(q.deQueue());
                }

                //tempQ.enQueue(qData);

                while(!q.isEmpty())
                        tempQ.enQueue(q.deQueue());

                int sortedData = tempQ.deQueue();

                sortQueue(tempQ);

                System.out.print(sortedData + ", ");
        }

        static public void main(String[] args) {
                Queue q = new Queue(5);
                q.enQueue(3); q.enQueue(5); q.enQueue(2); q.enQueue(1); q.enQueue(4);

                q.print();

                sortQueue(q);

                System.out.println();
        }
}

Tree Traversal Techniques

There are mainly two ways in which we can traverse a tree:
1. Breadth-First (or) Level Order Tree Traversal
2. Depth-First Tree Traversal

Breadth-First/Level Order Tree Traversal:
Here we traverse/print all the nodes available at an order, before going to next order
We go from top to bottom
                            1
             2                              3
   4               5           6                      7

For this tree, the Level Order Traversal is: 1, 2, 3, 4, 5, 6, 7

Algorithm:
a. Initialize a queue
b. enQueue root on to queue.

c. while queue is not empty
    deQueue the queue and print its contents
    push deQueue'd node's left and right nodes into queue

class LevelOrderTrav {
        static public void levelOrderTrav(TreeNode root) {
                if(root == null) {
                        System.err.println("Tree is empty...");

                        return;
                }

                ListQueue q = new ListQueue();
                q.enQueue(root);

                while(! q.isEmpty()) {
                        TreeNode node = q.deQueue();

                        System.out.print(node.getData() + ", ");

                        if(node.getLeft() != null)
                                q.enQueue(node.getLeft());

                        if(node.getRight() != null)
                                q.enQueue(node.getRight());
                }

                System.out.println();
        }

        static public void main(String[] args) {
                levelOrderTrav(TreeUtil.getTree());
        }
}

Depth-First Traversing Techniques:

These are again divided into 3 types, based on when the data(D) is printed.

1. PreOrder (DLR): Print Data, Traverse Left Tree and then Traverse Right Tree

2. InOrder(LDR): Traverse Left Tree, Print Data and then Traverse Right Tree

3. PostOrder(LRD): Traverse Left Tree, Traverse Right Tree and then Print data

Recursive way of traversing tree:

class RecTraversal {
        //DLR
        static public void recPreOrder(TreeNode node) {
                if(node != null) {
                        System.out.print(node.getData() + ", ");

                        recPreOrder(node.getLeft());
                        recPreOrder(node.getRight());
                }
        }

        //LDR
        static public void recInOrder(TreeNode node) {
                if(node != null) {
                        recInOrder(node.getLeft());
                        System.out.print(node.getData() + ", ");
                        recInOrder(node.getRight());
                }
        }

        //LRD
        static public void recPostOrder(TreeNode node) {
                if(node != null) {
                        recPostOrder(node.getLeft());
                        recPostOrder(node.getRight());
                        System.out.print(node.getData() + ", ");
                }
        }

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

                recPreOrder(node);
                System.out.println();

                recInOrder(node);
                System.out.println();

                recPostOrder(node);
                System.out.println();
        }
}
~                         

Post Order Binary Tree Traversal

Traversing a tree in Post order is a bit difficult.

class PostOrderTrav {
        static public void postOrderTrav(TreeNode root) {
                Stack stack = new Stack();

                if(root == null) {
                        System.err.println("TreeNode root is empty");
                        return;
                }

                do {
                        while(root != null) {
                                if(root.getRight() != null)
                                        stack.push(root.getRight());

                                stack.push(root);

                                root = root.getLeft();
                        }

                        root = stack.pop();

                        if(root.getRight() != null && root.getRight() == stack.peek()) {
                                stack.pop();
                                stack.push(root);
                                root = root.getRight();
                        } else {
                                System.out.println(root.getData());
                                root = null;
                        }


                } while(! stack.isEmpty());
        }

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

                postOrderTrav(root);
        }
}