package treesample.levelorder.recursive;
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class LevelOrderRecursive {
Node root;
public LevelOrderRecursive() { root = null; }
void LevelOrder()
{
int h = height(root);
int i;
for (i=1; i<=h; i++)
CurrentLevel(root, i);
}
int height(Node root) {
if (root == null)
return 0;
else {
int lheight = height(root.left);
int rheight = height(root.right);
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}
void CurrentLevel (Node root ,int level) {
if (root == null){
return;
}
if (level == 1){
System.out.print(root.data + " ");
}
else if (level > 1) {
CurrentLevel(root.left, level-1);
CurrentLevel(root.right, level-1);
}
}
public static void main(String args[])
{
LevelOrderRecursive tree = new LevelOrderRecursive();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.LevelOrder();
}
//There are basically two functions in this approach.
// One of them is used to print all nodes at a particular level (CurrentLevel),
// and another is used to print level order traversal of the tree (Levelorder).
//
//In the CurrentLevel function, we find the height of the tree and call the LevelOrder
// function for every level between 1 to height.
//In the LevelOrder function we pass two parameters level and root. we follow the below steps:
//First check if root is null then return.
//Check if level is equal to 1 then print the current root value.
//Now, call recursively call both the children of the current root with
// decrementing the value of level by 1.
//Time complexity: For a skewed tree, time complexity will be O(n^2).
//Space complexity: For a skewed tree space complexity will be O(n) and for a
}
TechInsiderStory is place where you can find basic knowledge of various technology and framework. TechInsiderStory is provide free knowledge on various technology and framework.
Tree-Traverse-Order-Level-Recursive
Tree Traverse In Order Recursive Approach And Display
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
public class TreeTraversalInOrderAndDisplay {
// Root of Binary Tree
Node root;
TreeTraversalInOrderAndDisplay() { root = null; }
/* Given a binary tree, print its nodes in inorder*/
void printInorder(Node node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
System.out.print(node.key + " ");
/* now recur on right child */
printInorder(node.right);
}
// Wrappers over above recursive functions
void printInorder() { printInorder(root); }
// Driver code
public static void main(String[] args)
{
TreeTraversalInOrderAndDisplay tree = new TreeTraversalInOrderAndDisplay();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
// Function call
System.out.println(
"\nTraversal of binary tree is ");
tree.printInorder();
//Time Complexity: O(N)
//Auxiliary Space: If we don’t consider the size of the stack for function
// calls then O(1) otherwise O(h) where h is the height of the tree.
}
}
SubArray Max Sum
public class SubArrayMaxSum {
public static void main(String[] args) {
int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 };
System.out.println("Maximum contiguous sum is "
+ sum(a));
}
public static int sum(int arr[]){
int sum1=Integer.MIN_VALUE,sum2=0,size=arr.length;
for(int i=0;i<size;i++){
sum2=sum2+arr[i];
if(sum1<sum2){
sum1=sum2;
}
if(sum2<0){
sum2=0;
}
}
return sum1;
}
}
Detect And Remove Loop from LinkList
import java.util.HashSet;
class LinkList3{
Node head;
Node sl;
Node ft;
class Node{
int data;
Node next;
public Node(int data,boolean flag, Node node){
this.data=data;
this.next=null;
}
@Override
public String toString() {
return "{"+this.data+"}";
}
}
public Node push(int data,boolean flag, Node node){
Node link=new Node(data,flag,node);
if(head==null){
head=link;
}else{
Node current=head;
while(current.next!=null){
current=current.next;
}
if(flag && node!=null){
link.next=node;
}
current.next=link;
}
return link;
}
public void display(){
Node current=head;
while(current!=null){
System.out.print(current);
current=current.next;
}
}
public boolean detectLoop1(){
HashSet set=new HashSet();
Node current=head;
boolean flag=false;
while(current.next!=null){
if(set.contains(current)){
flag=true;
break;
}
set.add(current);
current=current.next;
}
return flag;
}
public boolean detectLoop2(){
sl=head;
ft=head.next;
while(sl!=ft){
if(ft==null || ft.next==null){
return false;
}
sl=sl.next;
ft=ft.next.next;
}
return true;
}
public boolean removeLoop1(){
HashSet set=new HashSet();
Node previous=head;
Node current=head;
while(current!=null){
if(set.contains(current)){
previous.next=null;
return true;
}
set.add(current);
previous=current;
current=current.next;
}
return false;
}
public void removeLoop2(){
ft=head;
while(ft!=null){
Node ptr=sl;
while(ptr.next!=sl && ptr.next!=ft){
ptr=ptr.next;
}
if(ptr.next==ft){
ptr.next=null;
return;
}
ft=ft.next;
}
}
}
public class DetectLoop2 {
public static void main(String[] args) {
LinkList3 linkList3=new LinkList3();
linkList3.push(10,false,null);
LinkList3.Node push = linkList3.push(20, false, null);
linkList3.push(30,false,null);
linkList3.push(40,false,null);
linkList3.push(50,true,push);
boolean flag=false;
//linkList3.display();
// flag= linkList3.detectLoop1();
flag= linkList3.detectLoop2();
if(flag){
System.out.println("loop found");
}else{
System.out.println("loop not found");
}
//linkList3.removeLoop1();
linkList3.removeLoop2();
linkList3.display();
}
}
Binary Array Minimum Adjacent Swaps Required To Sort Binary Array
public class BinaryArrayMinimumSwap {
public static int minswaps(int arr[], int n)
{
int count = 0;
int numUnplacedZeros = 0;
for (int index = n - 1; index >= 0; index--)
{
if (arr[index] == 0)
numUnplacedZeros += 1;
else
count += numUnplacedZeros;
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 0, 0, 1, 0, 1, 0, 1, 1 };
System.out.println(minswaps(arr, 8));
//Space Optimized Solution: An auxiliary space is not needed.
// We just need to start reading the list from the back and keep track of number
// of zeros we encounter.
// If we encounter a 1 the number of zeros is the number of swaps needed
// to put the 1 in correct place.
//Time Complexity: O(n)
//Auxiliary Space: O(1)
}
}
Subscribe to:
Posts (Atom)