class LinkedList{
Node head;
static class Node{
int data;
Node next;
Node(int d){
data=d;
next=null;
}
}
public static LinkedList insertAtEnd(LinkedList list,int d){
Node newNode=new Node(d);
if(list.head==null){
list.head=newNode;
}
else{
Node temp=list.head;
while(temp.next!=null){
temp=temp.next;
}
temp.next=newNode;
}
return list;
}
public static LinkedList deleteByKey(LinkedList list, int key){
Node temp=list.head;
Node prev=null;
if(list.head.data==key)
list.head=list.head.next;
else{
while(temp!=null && temp.data!=key){
prev=temp;
temp=temp.next;
}
prev.next=temp.next;
}
return list;
}
public static void printAll(LinkedList list){
System.out.println("LinkedList: ");
Node temp=list.head;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
}
class LL {
public static void main(String[] args) {
LinkedList l=new LinkedList();
l=LinkedList.insertAtEnd(l,5);
l=LinkedList.insertAtEnd(l,4);
l=LinkedList.insertAtEnd(l,3);
l=LinkedList.insertAtEnd(l,2);
LinkedList.printAll(l);
l=LinkedList.deleteByKey(l,2);
LinkedList.printAll(l);
}
}
abstract class Queue{
Node head;
Node tail;
static class Node{ //FIFO
int data;
Node next;
Node(int d){
data=d;
next=null;
}
}
abstract boolean isEmpty(Queue q); //RETURN HEAD.NEXT
abstract int peek(Queue q); //RETURN HEAD.DATA
abstract Queue add(Queue q,int data); //ADD TO TAIL SO TAIL KEEPS INCREASING
abstract Queue deQueue(Queue q); //REMOVE FROM HEAD SO HEAD MOVES CLOSER TO TAIL AND THE SIZE DECREASES
}
abstract class Stack{
Node top;
static class Node{ //LIFO
int data;
Node next;
Node(int d){
data=d;
next=null;
}
}
abstract boolean isEmpty(Stack s); //RETURN TOP.NEXT
abstract int peek(Stack s); //RETURN TOP.DATA
abstract Queue push(Stack s,int data); //ADD TO FRONT I.E PREPEND AND MAKE TOP AS THE NEW NODE
abstract Queue pop(Stack s); //REMOVE FROM TOP AND SHIFT TOP TO TOP.NEXT
}
class BST{
Node root;
static class Node{ //REGULAR NODE SIMILAR TO LINKED LISTS BUT WITH LET AND RIGHT
int data;
Node left,right;
public Node(int data){
this.data=data;
left=right=null;
}
}
BST(){ //INITIALIZE ROOT TO NULL
root=null;
}
public Node insert(Node node,int value){
if(node==null){ //CHECK IF TREE IS EMPTY, INSERT AT ROOT
return new Node(value);
}
if(value<=node.data){ //IF VAL<ROOT.DATA INSERT AT LEFT SUBTREE
node.left=insert(node.left,value);
}
else if(value>node.data){ //IF VAL>ROOT.DATA INSERT AT RIGHT SUBTREE
node.right=insert(node.right,value);
}
return node; //RETURN ROOT OF THE TREE
}
public Node delete(Node node,int value){ //CHECK IF ROOT NODE IS NULL
if(node==null)
return null;
if(value<node.data){ //IF VAL<NODE.DATA PROCEED TO LEFT SUBTREE
node.left=delete(node.left,value);
}
else if(value>node.data){ //IF VAL>NODE.DATA GO TO RIGHT SUBTREE
node.right=delete(node.right,value);
}
else{ //ELSE CHECK IF LEFT OR RIGHT ARE EMPTY, OR BOTH ARE EMPTY.
if (root.left == null) //IF LEFT EMPTY RETURN RIGHT AND VICE VERSA
return root.right;
else if (root.right == null)
return root.left;
node.value=minValue(node.right); //INORDER SUCCESSOR //IF BOTH NODES EXIST THEN FIND THE MIN VALUE OF THE RIGHT SUBTREE(LEFT BRANCH OF THIS SUBTREE)
node.right=delete(node.right,node.data); //WE THEN DELETE THE INORDER SUCCESSOR
}
return node;
}
public int minValue(Node node){ //FUNCTION TO FIND THE MIN VALUE IN A SUBTREE
int minval=node.data; //MINVALUE WILL ALWAYS BE IN THE LEFTMOST LEAF NODE IN THE SUBTREE
while(node.left!=null){
minval=node.left.data;
node=node.left;
}
return minval;
}
public void traverse(Node node){ //INORDER=> LEFT MID RIGHT
if(node!=null){ //PREORDER=> MID LEFT RIGHT
traverse(node.left); //POSTORDER=> LEFT RIGHT MID
System.out.println(node.data);
traverse(node.right);
}
}
public boolean search(Node node,int value){
if(node==null){ //CHECK IF ROOT IS NULL(EMPTY TREE)
return false;
}
boolean isPresent=false; //FLAG TO CHECK THE PRESENCE
while(node!=null){ //ITERATE THROUGH IN A LINKED LIST FASHION
if(value<node.data){ //IF VAL<DATA GO LEFT BRANCH
node=node.left;
}
else if(value>node.data){ //IF VAL>DATA GO RIGHT BRANCH
node=node.right;
}
else{ //ELSEIF VAL==DATA THEN SET FLAG TO TRUE AND BREAK THE LOOP
isPresent=true;
break;
}
}
return isPresent;
}
}
class LinkedLists{
static class Node{
int data;
Node next;
Node(int data){
this.data=data;
next=null;
}
}
Node head;
public static LinkedList append(LinkedList list,int data){
Node new_Node=new Node(data);
if(list.head==null)
list.head=new_Node;
else{
Node temp=list.head;
while(temp!=null){
temp=temp.next!;
}
temp.next=new_Node;
}
return list;
}
public static LinkedList delete(LinkedList list,int key){
Node temp=list.head;
Node prev=null;
if(list.head.data==key){
list.head=list.head.next;
}
else{
while(temp!=null && temp.data!=key){
prev=temp;
temp=temp.next;
}
prev.next=temp.next;
}
return list
}
}
class bst{
static class Node{
int data;
Node left,right;
Node(int data){
left=right=null;
}
}
Node root;
bst(){
root=null;
}
public static Node insert(Node root,int data){
if(root==null)
return new Node(data);
else if(data<=root.data){
root.left=insert(root.left,data);
}
else if(data>root.data){
root.right=insert(root.right,data);
}
return root;
}
public static Node delete(Node root,int key){
if(root==null)
return null;
else if(key>root.data){
root.right=delete(root.left,key);
}
else if(key<=root.data){
root.left=delete(root.left,key);
}
else {
if(root.left==null)
return root.right;
if(root.right==null)
return root.left;
root.data=minvalue(root.right);
root.right=delete(root.right,root.data);
}
}
public static int minvalue(Node root){
Node temp=root.left;
int min=temp.data;
while(temp!=null){
min=temp.left.data;
temp=temp.left;
}
return min;
}
public static void traverse(Node root){
if(root!=null){
traverse(root.left);
s.op=root.data;
traverse(root.right);
}
}
public static boolean search(Node root,int val){
if(root!=null){
return false;
}
while(root!=null){
if(val>root.data){
root=root.right;
}
else if(val<root.data){
root=root.left;
}
else{
return true;
break;
}
}
return false;
}
}
