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.

	import java.util.*;
	/** * Created by laxmikadariya on 6/10/18. */public class Graph {
	int V;
	LinkedList<Integer> adj[];
	Graph(int v)
	{
	V=v;
	adj = new LinkedList[V];
	for(int i = 0;i<V;i++)
	{
	adj[i] = new LinkedList();
	}
	}
	void add_edge(int parent ,int child)
	{
	this.adj[parent].add(child);
	}
	void call_DFS_recursive(int start, boolean[] visited)
	{
	visited[start] = true;
	System.out.println(start);
	Iterator<Integer> it = adj[start].listIterator();
	while(it.hasNext() )
	{
	int element = it.next();
	if(!visited[element])
	{
	call_DFS_recursive(element,visited);
	}
	}
	}
	void DFS_iterative(int start)
	{
	boolean visited[] = new boolean[V];
	Stack<Integer> stack = new Stack();
	stack.push(start);
	visited[start] = true;
	while(!stack.empty())
	{
	int element = stack.pop();
	System.out.println(element);
	Iterator<Integer> it = adj[element].listIterator();
	while(it.hasNext())
	{
	int value = it.next();
	if(!visited[value]) {
	stack.push(value);
	visited[value] = true;
	}
	}
	}
	}
	void DFS(int start)
	{
	boolean [] visited = new boolean[V];
	call_DFS_recursive(start,visited);
	}
	void BFS(int start)
	{
	boolean visited[] = new boolean[V];
	Queue<Integer> queue = new LinkedList<Integer>();
	queue.add(start);
	visited[start]=true;
	while(queue.size() !=0)
	{
	int element = queue.remove();
	System.out.println(element);
	Iterator<Integer> it = adj[element].listIterator();
	while(it.hasNext())
	{
	int top = it.next();
	if(!visited[top] )
	{
	queue.add(top);
	visited[top] =true;
	}
	}
	}
	}
	public static void main(String []args)
	{
	Graph g = new Graph(6);
	g.add_edge(0,1);
	g.add_edge(0,2);
	g.add_edge(1,3);
	g.add_edge(1,4);
	g.add_edge(1,0);
	g.add_edge(2,4);
	g.add_edge(2,0);
	g.add_edge(3,4);
	g.add_edge(3,5);
	g.add_edge(3,1);
	g.add_edge(4,2);
	g.add_edge(4,3);
	g.add_edge(4,5);
	g.add_edge(5,4);
	g.add_edge(5,3);
	// g.DFS(0);// g.DFS_iterative(0); g.BFS(0);
	}
	}

view raw BFS_DFS_JAVA.java hosted with ❤ by GitHub

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





}

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)