Binary Tree in Java

Binary Tree or Binary Search Tree
Trees: Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are hierarchical 
data structures. Elements with no children are called leaves.

package datastructure.tree;
public class BinaryTreeTest {
    static class Node {
        Node left;
        Node right;
        int data;
        public Node(int d) {
            this.data = d;
        }
    }

    static Node root = null;
    public static void main(String[] args) {
        root = new Node(50); //Making 5 as Root node    

        BinaryTreeTest object = new BinaryTreeTest();
        object.startFunctions();
        System.out.println("Total Node Count: "+object.countNodes(root));
        System.out.println("Search Node 60: "+object.search(root, 60));
    }

    public void startFunctions() {        
        System.out.println("Building tree with root value " + root.data);
        insert(root, 30);
        insert(root, 20);
        insert(root, 40);
        insert(root, 70);
        insert(root, 60);
        insert(root, 80);
        System.out.println("Traversing Tree InOrder");
        printInOrder(root);        
        System.out.println("Traversing Tree PreOrder");
        printPreOrder(root);        
        System.out.println("Traversing Tree PostOrder");
        printPostOrder(root);
    }

    public void insert(Node node, int value) {
        if(value<node.data) { //To go to left side
            if(node.left == null) {
                node.left = new Node(value);
                System.out.println("  Inserted " + value + " to left of " + node.data);
            }
            else {
                insert(node.left, value);
            }
        } 
        else if(value>node.data) { //To go to right side
            if(node.right == null) {
                node.right = new Node(value);
                System.out.println("  Inserted " + value + " to right of "+ node.data);
            } else {
                insert(node.right, value);
            }
        }
    }
    public void printInOrder(Node node) {
        if(node != null) {
            printInOrder(node.left);
            System.out.println("  InOrder Traversed " + node.data);
            printInOrder(node.right);
        }
    }
    public void printPreOrder(Node node) {
        if(node != null) {
            System.out.println("  PreOrder Traversed " + node.data);
            printPreOrder(node.left);
            printPreOrder(node.right);
        }
    }
    public void printPostOrder(Node node) {
        if(node != null) {
            printPostOrder(node.left);
            printPostOrder(node.right);
            System.out.println("  PostOrder Traversed " + node.data);
        }
    }
    private int countNodes(Node r) {
        if(r == null)
            return 0;
        else {
            int count = 1;
            count += countNodes(r.left);
            count += countNodes(r.right);
            return count;
        }
    }
    private boolean search(Node r, int val) {
        if(r.data == val)
            return true;
        if(r.left != null){
            if(search(r.left, val))
                return true;
        }
        if(r.right != null){
            if(search(r.right, val))
                return true;
        }
        return false;         
    }

    boolean identicalTrees(Node root1, Node root2) {        
        if(root1 == null && root2 == null)
            return true;

        if(root1 != null && root2 != null) 
            return (
                    root1.data == root2.data && 
                    identicalTrees(root1.left, root2.left) && 
                    identicalTrees(root1.right, root2.right)
                 );        
        return false;
    }
}

//Output
Building tree with root value 50
  Inserted 30 to left of 50
  Inserted 20 to left of 30
  Inserted 40 to right of 30
  Inserted 70 to right of 50
  Inserted 60 to left of 70
  Inserted 80 to right of 70

Traversing Tree InOrder
  InOrder Traversed 20
  InOrder Traversed 30
  InOrder Traversed 40
  InOrder Traversed 50
  InOrder Traversed 60
  InOrder Traversed 70
  InOrder Traversed 80

Traversing Tree PreOrder
  PreOrder Traversed 50
  PreOrder Traversed 30
  PreOrder Traversed 20
  PreOrder Traversed 40
  PreOrder Traversed 70
  PreOrder Traversed 60
  PreOrder Traversed 80

Traversing Tree PostOrder
  PostOrder Traversed 20
  PostOrder Traversed 40
  PostOrder Traversed 30
  PostOrder Traversed 60
  PostOrder Traversed 80
  PostOrder Traversed 70
  PostOrder Traversed 50

Total Node Count: 7
Search Node 60: true


Properties:
1) The maximum number of nodes at level ‘L’ of a binary tree is 2 Power(L-1). Root is always at Level 1. Hence only 1 Node at Root. 
Max Node at Level 3 are 4. Here 20, 40, 60, 80 are at level 3. Here level is number of nodes on path from root to the node (including root and node). 

2) Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1. Here height of a tree is maximum number of nodes on root to leaf path. 
Height of a leaf node is considered as 1.

Full Binary Tree A Binary Tree is full if every node has 0 or 2 children. Above all images are full binary tree.
A degenerate (or pathological) tree: A Tree where every internal node has one child. Such trees are performance-wise same as linked list. 

Stack Data Structure Using Array in Java

//Stack DataStructure Using Array
package stack;
public class MyStack {
    private int maxSize;
    private long[] stackArray;
    private int top;

    public MyStack(int s) {
        maxSize = s;
        stackArray = new long[maxSize];
        top = -1;
    }
    public void push(long j) {
        if(isFull()) {
            System.out.println("Stack is Full");
        } else {
            top++;
            stackArray[top] = j;
        }
    }
    public long pop() {
        if(top < 0) {
            System.out.println("Stack Underflow");
            return 0;
        }else{
            long item = stackArray[top];
            top--;
            return item;
        }
    }
    public long peek() {
        return stackArray[top];
    }
    public boolean isEmpty() {
        return (top == -1);
    }
    public boolean isFull() {
        return (top == maxSize-1);
    }

    public static void main(String[] args) {
        MyStack theStack = new MyStack(10); 
        theStack.push(10);
        theStack.push(20);
        theStack.push(30);
        theStack.push(40);
        theStack.push(50);

        while (!theStack.isEmpty()) {
            long value = theStack.pop();
            System.out.println("Values are: "+value);            
        }
        System.out.println("Is Empty Now: "+theStack.isEmpty());  //true
    }
}

//Output
Values are: 50
Values are: 40
Values are: 30
Values are: 20
Values are: 10
Is Empty Now: true

SinglyLinkedList Algorithm in Java

A Singly Linked List, in its simplest form, is a collection of nodes that together form a linear ordering.
    A node has two parts: Element and Pointer (or Data and Reference).
    Each element in the node represents DATA_VALUE of that Node. The Pointer of each node has reference to another Node 
    like STEPS of a LADDER. So NULL Pointer means a TAIL Node, that means End of Linked list. Moving from one node to 
    another by following a next reference is known as Link hopping or Pointer hopping. The first and last node of a linked 
    list usually are called the head and tail of the list. Also remember DATA_VALUE can be anything like a "Person" Object 
    having many attributes or any Wrapper class object.

LinkedList Program:

-----------------------------------------------------------
package datastructure.linkedlist;
//Author Deepak Kumar Modi
public class Node {
    public int data;
    public Node next;
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    public String toString(){
        return data+"";
    }
}
-----------------------------------------------------------
package datastructure.linkedlist;
//Author Deepak Kumar Modi
public class SinglyLinkedList {
    public Node start;  //means header node
    public int size;
    
    public SinglyLinkedList(){
        start=null;   //start means header node
        size=0;
    }
    public void addAtFirst(int number){
        Node temp=new Node();
        temp.setData(number);  //Make temp new node
        if(size==0){           //List is empty, create head node
            temp.setNext(null);  //Make first node, so reference is null.
            start=temp;          //make temp as header node
        }else{
            temp.setNext(start);    //new node is complete now with pointing to header       
            start=temp;             //make new node as header 
        }
        size++;
    }
    public void addAtEnd(int number){
        Node temp=new Node();
        temp.setData(number);       //temp is new node
        
        if(size==0){                //List is empty, create head node
            temp.setNext(null);
            start=temp;
        }else{  
            Node tempHead=start;        //store header node "start" to a temp node as "tempHead"
            while(start.getNext()!=null){
                start=start.getNext();
            }
            start.setNext(temp);   //temp.setNext will be null by default.
            start=tempHead;        //Since start pointer has moved to the end, store the old tempHead node to start again.
        }
        size++;
    }
    
    public Node getNodeAt(int nodePos) {
        if(nodePos>=size || nodePos<0){
            return null;
        }
        Node temp = start; //Move start pointer to front
        for(int counter=0; counter<nodePos; counter++){
            temp = temp.next;  //Move till the node position
        }
        return temp;
    }
    public void removeAtPosition(int position) {
        System.out.println("\nRemoving from position: "+position);
        Node temp = getNodeAt(position-1);            
        temp.setNext(temp.getNext().getNext());  //here temp.getNext() is getting removed/reference removed from LinkedList.
        size--;
    }
    public void reverseList() {
        System.out.println("\nReversing the List now.");
        if(size<=1){
            System.out.println("Not required, only one Node.");
        }
        Node previousNode = null; 
        Node currentNode = start; 
        Node nextNode = null;
        
        while(currentNode.next != null) {
            nextNode = currentNode.next;
            currentNode.next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
        currentNode.next = previousNode;
        start = currentNode;
    }
    
    public Node getFirst(){
        return getNodeAt(0);
    }

    public Node getLast(){
        return getNodeAt(size-1);
    }

    public boolean contains(int number){
        Node temp = start; //Move pointer to front
        for(int counter=0;counter<size;counter++){
            if(temp.getData()==number)
                return true;
            temp = temp.next;
        }
        return false;
    }
    public void clear(){    
        System.out.println("\nRemoving all the elements in the List: "+size);
        start = null;
        size=0;
    }
    public void displayList(){    
        Node temp=start;  //Save start into a temp Variable
        if(size>0)
            System.out.println("Size: "+size);
        else
            System.out.println("No elements to display.");
        
        for(int i=0;i<size && temp!=null;i++){
            System.out.print(temp.getData()+", ");
            temp=temp.getNext();
        }
    }
}
----------

package datastructure.linkedlist;
//Author Deepak Kumar Modi
public class SinglyLinkedListTest {
    public static void main(String a[]){
        SinglyLinkedList list=new SinglyLinkedList();
        System.out.println("Adding at Begining...");
        list.addAtFirst(10); list.addAtFirst(60);  list.addAtFirst(3); list.addAtFirst(2); list.addAtFirst(70);
        list.displayList(); 
        System.out.println("\nlist.getNodeAt(3): "+list.getNodeAt(3));
        list.clear();
        list.displayList();
        
        System.out.println("\nAdding at End...");
        list.addAtEnd(10);   list.addAtEnd(60);    list.addAtEnd(3);   list.addAtEnd(2);   list.addAtEnd(70);
        list.displayList();
        
        list.reverseList();
        list.displayList();        
        
        System.out.println("\nGet Last Element: list.getLast(): "+list.getLast());
        System.out.println("\nContent Check: list.contains(3): "+list.contains(3));
        System.out.println("Content Check: list.contains(13): "+list.contains(13));
        
        System.out.println("\nNode Check: list.getNodeAt(3): "+list.getNodeAt(3));
        System.out.println("Node Check: list.getNodeAt(10): "+list.getNodeAt(10));
        
        list.removeAtPosition(3);
        list.displayList();
        System.out.println("\nNode Check: list.getNodeAt(3): "+list.getNodeAt(3));
    }
}
-----------------------------------
//Output:
Adding at Begining...
Size: 5
70, 2, 3, 60, 10, 
list.getNodeAt(3): 60

Removing all the elements in the List: 5
No elements to display.

Adding at End...
Size: 5
10, 60, 3, 2, 70, 
Reversing the List now.
Size: 5
70, 2, 3, 60, 10, 
Get Last Element: list.getLast(): 10

Content Check: list.contains(3): true
Content Check: list.contains(13): false

Node Check: list.getNodeAt(3): 60
Node Check: list.getNodeAt(10): null

Removing from position: 3
Size: 4
70, 2, 3, 10, 
Node Check: list.getNodeAt(3): 10
-----------------------------------------------------------
Another useful algorithm for Singly Linked List:
Practice Question: Determine whether a linked list contains a cycle.
    
Ans: Traversal of a linked list with a cycle will never end, so there needs to be some method to keep track 
    of what nodes have been encountered. One idea is to mark nodes that have been seen, either by adding a flag 
    to the node itself or storing information about the node in a separate data structure. Unfortunately, this 
    method requires modification of the node and/or additional space.

    With linked list problems, the solution usually takes advantage of multiple pointers. How can we use another 
    pointer to help us out? The previous problem advanced two pointers at a fixed interval between each other, 
    but that doesn’t seem to help. A better idea is to advance the pointers at two different speeds.

    One pointer will travel at twice the speed of the other, so in an acyclic list, the fast one will reach the end. 
    However, in a cyclic list, both pointers loop endlessly, but the faster pointer will lap the slower pointer at 
    some point, so if the faster pointer ever catches up to the slower pointer, the list has a cycle.

    To make one pointer “faster” than the other, just advance it two nodes instead of one. However, be aware of null 
    pointers.

The running time for this algorithm is O(n). For the ACYCLIC case, the faster pointer will reach the last node 
after traversing the entire list. For the CYCLIC case, the slower pointer will only go around a loop at most once, 
and the faster pointer will only go through a loop at most twice, so in the worst case 3n nodes are examined, which 
is still an O(n) algorithm. 

Code:
----------------
public static boolean hasCycle(Node head) {
    Node fast = head;
    Node slow = head;
 
    while (fast != null && slow != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
 
        if (slow == fast) {
            return true;
        }
    } 
    return false;
}
==================END=======================