Monday, June 11, 2018

Breadth first search(BFS), Depth first Search(DFS) both iterative and recursive in Java

Graph can be represented in two ways:
 1)adjacency matrix
  2) adjancency list


Note here we create array of linkedlist. Array are of size length vertices.
Each array has all its childrens so each array is linkedlist  of size vertices V.






Saturday, June 9, 2018

Trees in java

Simple Trees in Java:

class node1
{
   int data;
    node1 left;
    node1 right;

    node1(int data){
        this.data = data;
        this .left = null;
        this.right = null;
    }

    void inorder(){
        if(left != null) {
            left.inorder();
        }
            System.out.println(this.data);
        if(right != null)
            right.inorder();

    }
}

public class Tree {

    void inorder(node1 root) {
        if (root!= null) {

            inorder(root.left);
            System.out.println(root.data);
            inorder(root.right);
        }
    }

    public static void main(String[] args)
    {
        node1 root1 = new node1(5);
        root1.left = new node1(3);
        root1.right = new node1(7);
        root1.left.left = new node1(2);
        root1.left.right = new node1(4);
        root1.right.left = new node1(6);
        root1.right.right = new node1(8);

        Tree tree = new Tree();
        tree.inorder(root1);

        root1.inorder();

    }
}


For addition of add_item function for creating binary tree:
Note to use in lower class if root has to be passed otherwise in the upper class of only item has 
to be passed as root should be referenced with object.



class node1
{
   int data;
    node1 left;
    node1 right;

    node1(int data){
        this.data = data;
        this .left = null;
        this.right = null;
    }

  void add_node(int item)
  {
      if(item < this.data )
      {
          if(this.left == null)
          {
              this.left = new node1(item);
          }

          else{
              this.left.add_node(item);
          }
      }
      else{
          if(this.right == null)
          {
              this.right = new node1(item);
          }
          else          {
              this.right.add_node(item);
          }
      }
  }


}

public class Tree {

    void inorder(node1 root) {
        if (root!= null) {

            inorder(root.left);
            System.out.println(root.data);
            inorder(root.right);
        }
    }

    void add_node(node1 root,int item)
    {
        if(root == null)
            root = new node1(item);
        else{
            if(item < root.data )
                if(root.left == null)
                    root.left = new node1(item);
                else                {
                    add_node(root.left,item);
                }
            else{
                if(root.right == null)
                    root.right = new node1(item);
                else {
                    add_node(root.right, item);
                }
            }
        }
    }

    public static void main(String[] args)
    {
        node1 root1 = new node1(5);
//        root1.add_node(3);//        root1.add_node(2);//        root1.add_node(1);//        root1.add_node(6);//        root1.add_node(8);//        root1.add_node(7);




        Tree tree = new Tree();


        tree.add_node(root1,3);
        tree.add_node(root1,2);
        tree.add_node(root1,1);
        tree.add_node(root1,6);
        tree.add_node(root1,8);
        tree.add_node(root1,7);
        tree.add_node(root1,9);
        tree.inorder(root1);


    }
}

Linked List creation in Java from scratch

1. Simple linked list creation statically:

class node{
    int data;
    node next;

    node(int item){
        data = item;
        next = null;
    }


}

class linked_list{

    node create_list()
    {
        node head = new node(2);
        head.next = new node(3);
        head.next.next = new node(4);
        head.next.next.next = new node(5);
        return head;

    }


    void get_list(node head)
    {
        node current = head;
        while(current != null)
        {
            System.out.println(current.data);
            current = current.next;
        }

    }

}

public class list {


    public static void main(String[] args)
    {

        linked_list start = new linked_list();
        node head = start.create_list();
        start.get_list(head);
    }


}

2. Simple within the same class:

class list
{
    int data;
    list next;
    list(int date)
    {
        data = date;
        next = null;
    }
}
public class graph {
    void add_data(list root,int item)
    {
        list current = root;
        while(current.next != null)
        {
            current = current.next;

        }
        current.next = new list(item);

    }

    void get_data(list root)
    {
        list current = root;
        while(current != null)
        {
            System.out.println(current.data);
            current = current.next;
        }
    }



    public static void main(String[] args)
    {
        list root = new list(5);

        graph obj = new graph();
        obj.add_data(root,3);
        obj.add_data(root,4);
        obj.add_data(root,7);

        obj.get_data(root);
    }
}





2.With recursive insert:

Note to always store head in an object so that each time it doesnot change. Otherwise we need to
keep track of head and end seperately.

class node{
    int data;
    node next;

    node(int item){
        data = item;
        next = null;
    }

    public int getData() {
        return data;
    }

    public node getNext() {
        return next;
    }

    public void setData(int data) {
        this.data = data;
    }

    public void setNext(node next) {
        this.next = next;
    }
    public void insert_number(int data)
    {
        if(next == null){
            next = new node(data);

        }

        else{
            next.insert_number(data);
        }
    }
}

class linked_list{
    node head;

    linked_list(){
        head = null;
    }
    

    void insert_node(int data){
        if(head == null)
        {
            head = new node(data);
        }
        else{
            head.insert_number(data);
        }
/////or even can be done without recursion
//   note the n.next should be used.
/// public void insert_number(int data)
//{
//       node end = new node(data);
//  
      node n = this;//      
  while(n.next!= null)
//       {
//            n = n.next;
//        }
//        n.next = end;
//    }


}
    void get_list()
    {
        node current = head;
        while(current != null)
        {
            System.out.println(current.data);
            current = current.next;
        }

    }

}

public class list {


    public static void main(String[] args)
    {

        linked_list start = new linked_list();


        start.insert_node(2);
        start.insert_node(3);
        start.insert_node(4);
        start.insert_node(5);
        start.insert_node(6);
        start.insert_node(7);

        start.get_list();
    }





}




3: To keep track of head and end seperately:

class node{
    int data;
    node next;

    node(int item){
        data = item;
        next = null;
    }

    public int getData() {
        return data;
    }

    public node getNext() {
        return next;
    }

    public void setData(int data) {
        this.data = data;
    }

    public void setNext(node next) {
        this.next = next;
    }

}

class linked_list{
    node head;
    node end;

    linked_list(){
        head = null;
        end = head;
    }


    void insert_node(int data){
        if(head == null)
        {
            head = new node(data);
            end = head;
        }
        else{
            node nptr = new node(data);
            end.setNext(nptr);
            end = nptr;

        }


    }
    void get_list()
    {
        node current = head;
        while(current != null)
        {
            System.out.println(current.data);
            current = current.next;
        }

    }

}

public class list {


    public static void main(String[] args)
    {

        linked_list start = new linked_list();


        start.insert_node(2);
        start.insert_node(3);
        start.insert_node(4);
        start.insert_node(5);
        start.insert_node(6);
        start.insert_node(7);

        start.get_list();
    }





}



So overall with just only one class node is 

class node{
    int data;
    node next;

    node(int item){
        data = item;
        next = null;
    }

   
    public void insert_number(int data)
    {
       node end = new node(data);
        node n = this;
        while(n.next!= null)
        {
            n = n.next;
        }
        n.next = end;
    }

    void get_list()
    {
        node current = this;
        while(current != null)
        {
            System.out.println(current.data);
            current = current.next;
        }

    }
}



public class list {


    public static void main(String[] args)
    {

       node start = new node(1);


        start.insert_number(2);
        start.insert_number(3);
        start.insert_number(4);
        start.insert_number(5);
        start.insert_number(6);
        start.insert_number(7);

        start.get_list();
    }





}

Saturday, June 2, 2018

Inserting of elements in Binary search tree with minimal tree creation in Python

class node:
    def __init__(self,val):
        self.value = val
        self.left = None        self.right = None
def insert_node(val,root):
    if(val<root.value):
        if(root.left is None):
            root.left = node(val)
        else:
            insert_node(val,root.left)

    else:
        if(root.right is None):
            root.right = node(val)
        else:
            insert_node(val,root.right)

def inorder(root):
    if(root):
        print(root.value)
        inorder(root.left)
        inorder(root.right)

def minimal_tree(arr,start,end):
    if(start>end):
        return None    mid = (start+end)//2    root = node(arr[mid])
    root.left = minimal_tree(arr,start,mid-1)
    root.right = minimal_tree(arr,mid+1,end)

    return root

root = node(3)

x= [5,4,1,2]
for i in x:
    insert_node(i,root)

inorder(root)
y = [1, 2, 3, 4, 5 ,6 ,7, 8,9]




test = minimal_tree(y,0,len(y)-1)
print(test.value)
inorder(test)