Traversal of Binary Search Tree

Before we move , lets clear few concepts:-

Visiting a node :- This means doing something with the node like displaying, writing etc.

Traversing :- This means visiting each node in a specified order in a binary search tree or binary tree.

We can traverse in three ways using binary tree (we can perform these operations on binary search tree also)

1) In Order

2) Pre Order

3) Post Order
















In-Order Traversal:-

private void inOrder(Node localRoot)

{

if(localRoot != null)

{

inOrder(localRoot.leftChild); 

System.out.print(localRoot.data);

inOrder(localRoot.rightChild);

}

}

Take the example of the above figure, we will perform the in-order traversal using below steps:-

(1) We pass node A

(2) We further go to node B

(3) We further go to left child of node B which returns null.

(4) We print node B

(5)  We further go to right child of node B which returns null.

6) We come back and print node A

7) Repeat steps 2,3,4,5 for node C

8) In-Order traversing finishes.

We can use below example two study the two more options for the traversal options:-

private void preOrder(Node localRoot)

{

if(localRoot != null)

{

System.out.print(localRoot.data);

preOrder(localRoot.leftChild); 

preOrder(localRoot.rightChild);

}

}

Result : *A+BC

private void postOrder(Node localRoot)

{

if(localRoot != null)

{

System.out.print(localRoot.data);

postOrder(localRoot.leftChild); 

postOrder(localRoot.rightChild);

}

}

Result : ABC+*

Finding Maximum and Minimum value in a binary search tree:-

If we use the logic of find in binary search tree and keep going left till the node has no left children, then that is the minimum value in a binary search tree.


If we use the logic of find in binary search tree and keep going right till the node has no right  children, then that is the maximum value in a binary search tree.

Binary Search Tree

Binary Tree:-

We use binary tree because it combines the advantages of array and linked list both and also overcome disadvantages of both.

Advantages/disadvantages for array:-

1) Search is fast in an ordered array as we can use the approach of doing search using binary operation.
2) Insertion is slow in an array if the array is sorted. We have to first reach the place where we need to insert and then move the other required values.
3) Same applies to deletion also like insertion.

Advantages/disadvantages for linkedlist:-

1) Search is slow as we have to go through every node even if the linked list is sorted.
2) Insertion & deletion are fast as if we find the correct place to insert/delete all we have to do is change some reference of the first and last element

Trees :- They have both. Fast search and fast insert , delete.

Many kinds of trees are there, but we are talking about binary trees.Some terminologies in tree data structure:-

1) Path :- going from one node to another node.
2) Root :- Node at top of the tree.There is only one root in a tree.
3) Parent :- which has a child.
4) Child
5) Leaf :- A node which doesn't have any child.
6) Subtree
7) Visiting :-

Tree is a binary tree if every node can have atmost 2 children.

Binary search tree :- A tree will be called binary search tree if it has atmost 2 children and left child is lesser than parent and right child bigger than parent.

Unbalanced tree :- which do not have both children.

Binary search tree in Java :-

We can think of binary search tree as collection of object connected to each other through reference and structured in a parent-child relationship following the principal of binary search tree mentioned above.

Below are the steps to create a binary search tree:-

Step1 :-

Create a class whose objects can be used as nodes.

public class Node{

int key;      //every node has a key value

String data;     //this variable can carry any data. This data can be some other object also like parent.

//Every node will carry reference to its child (left & right)

Node leftChild;

Node rightChild;

}

Step2 :-

Next step is to create a program where we can play with these nodes and join them using binary search tree principal. We will call this class as Tree.

public class Tree{

Node root; // We will create this class variable for the root.

//To create a tree and play with nodes, we will write 3 methods

/*

* 1) Find

* 2) Insert

* 3) Delete

* */

public Node find(int key){

if(root==null)

return null;

Node current = root;

while(current.key!=key){

if(current.key>key){

current = current.rightChild;

}else{

current = current.leftChild;

}

if(current==null) {

return null;

} 

}

return current;

}

//------------------------------------------------------//

public void insert (int key, String data){

//First of all we will create a node

Node newChild = new Node();

newChild.key=key;

newChild.data=data;

//If the root is empty, we will make new child node as root.

if(root==null)

root = newChild;

Node current = root;

Node parent=null;

while(true){

parent=current;

if(current.key>key){

current=current.leftChild;

if(current==null){

parent.leftChild=newChild;

return;

}

}else if(current.key<key){

current=current.rightChild;

if(current==null){

parent.rightChild=newChild;

return;

}

}

}

}

}

Stack & Queues

Stacks:-

Analogy to stack is --> as you keep getting the letters, you keep putting them one over the another. This is called stacking.It follows the principle "Last in first out".

Underlying data structure can be array. Important methods of a stack are :-

1) Push --> to add something
2) Pop --> To remove something
3) Peek --> Get the top most element
4) isEmpty
5) isFull

In java we have a class -- Stack which can perform these operations and also has one more method called search (Object o)

Error Handling :- we need to take care of error handling when dealing with push() and pop() method as they can throw exception. Push when stack is full and pop when stack is empty.

Efficiency :- O(1) as one item is poped and pushed at a time.

Queues:- (We will discuss this in terms of Java API)

Analogy to queue is --> We can think of queue as line of people standing at some register to buy something.Queue is more of a British word I guess. It follows the principle of FIFO -- "First In First Out".

To visualize queue in form of an array, as items start inserting, index 0 will be the head of the queue in this case and say we insert insert 10 items, so in that case index 9 will be tail.

To add a new item we will simply one more item to the array and tail pointer will move to index 10

To remove a item, it has to be removed from head only to follow the queue principal for FIFO. Sp if we remove an item from queue, head pointer will move to index 1

Circular Queue :-

Now if we continue the above process of addition & removal from the queue, then in that case, a situation will come when tail will reach end of the array and head of the array also move up in the array after few deletions, then in that case tail pointer can go to index 0 and head will continue to be where it was. After few deletions and insertion, head can again come back behind tail in the array and this process will continue and utilize the array space in best possible way. We can this kind of queue as circular queue.

Priority Queue:-

In priority queue, we insert items in a queue in specific order such that say --> say largest number always remain at the rear and smallest number always remain at the front.

There is a better way to implement priority queue using heap sort.

Efficiency of priority queue:-

Insertion --> O(N)
Deletion --> O(1)




Below stuff more to do with Java implementation of queue. Refer other links.


Some important points to remember:-

1) A queue has a head and a tail
2) A new element is added to the tail and elements to-be processed are taken from the head as this follows the order in which elements were inserted.
3) In java implementation of Queue, they do apply duplicate insertion as it is the order in which elements are inserted which matter and not the value.

Queue interface has three child interfaces:-

1) Dequeue
2) BlockingQueue
3) BlockingDequeue and there some more which have been introduced with new java version which we are not going to discuss in this thread.




Queue can be implemented using both array and linked list.

In java, queue is an interface.  This interface has to be implemented by some underlying class:-

1) Stack :-

We can implement queue using 2 stacks. Push() or enqueue in queue is a common operation in both stack and queue as in both of them, we have to add element.

Problem comes, when we have to pop or dequeue the stack since in stack, we follow LIFO and in queue,

2) LinkedList
3) Array

For more practice stuff , we will refer this guide --> http://www.codejava.net/java-core/collections/java-queue-collection-tutorial-and-examples#WhatIsQueue

Insertion Sort

Insert sort can be understood using the analogy of playing game of cards like rummy. In the cards game , initially we get some x number of cards. We take these cards and sort them in our hands from left to right in ascending order. After this we start the playing where as and when we get a new card, we take that card, start comparing it from right to left in our hands and insert this new card wherever it fit as per it value. This is insertion sort.

In case of sorting an array using insertion sort, we basically start from position 1 and compare it with position 0. Swap these positions --> smaller goes left and bigger goes right. After this move on to position 2 and compare it with both position 0 & 1 and insert element at position 2 where it should and again repeat the same process till we complete the whole array.

 public static int[] doInsertionSort(int[ ] input){

         

        int temp;

        for (int i = 1; i < input.length; i++) {

        System.out.println("This is the value " + i);

            for(int j = i ; j > 0 ; j--){

            System.out.println("This is the value " + i);

                if(input[j] < input[j-1]){

                    temp = input[j];

                    input[j] = input[j-1];

                    input[j-1] = temp;

                }

            }

        }

        return input;

    }

Efficiency :-

Efficiency of insertion sort is O(N*N), however, if most of the data in a list/array is almost sorted, than it works very first.Good for list/array which are slightly out of order.