In a non-Empty binary tree Number of nodes of degree two is one less than number of leaf nodes

In a non-Empty binary tree
I.e a binary tree where every node has 2 child nodes or 0 child nodes
or a binary tree where every node has a degree 2 or is a leaf node

To prove : Number of nodes of degree two is one greater than number of leaf nodes
let n0 = no of leaf nodes
n1 = no of nodes with degree 2

then to prove that :
n0 = n1 + 1


Lets go about solving this problem with a simple imagination
Let assume a healthy binary tree to be one where each node is just healthy enough to give rise to 2 other nodes.
But due to some environmental complications, the tree gets diseased or little mutated i.e now every node either give rise to 2 nodes or none at all. So it's kind of saying that the nodes have now developed a flip-flop diseased nature.

Proof:
Let Nd denote nodes having dual nature, I.e which replicate into 2
Let Ns denote nodes having singular nature, I.e nodes which do not replicate at all

Let Kth level of tree has N1 dual nature nodes

So k+1 th level number of healthy nodes = 2*N1
but since the tree is diseased so
k+1 th level has nodes = ( 2*N1 – a1 ) + a1

where a1 is the nodes of nodes got diseased, So incapable of any further reproduction into duality

At level = k + 2
number of healthy nodes = 2 * ( 2N1 – a1 )
= 4*N1 – 2a1
but the tree is non-healthy so say b1 nodes again get diseased
so k+2 level nodes can be written as

k+2 has nodes = (4N1 – 2 a1 – b1 ) + b1
where b1 is the latest number of nodes to have got diseased, So incapable of any further reproduction into duality.

Extending the same logic at next level
At level = k + 3
number of healthy nodes = 2 * ( 4N1 – 2a1 – b1 )
= 8N1 – 4a1 -2b1

but the tree is non-healthy so, say, c1 nodes again get diseased
so k+3 level nodes can be written as
k + 3 has nodes = ( 8N1 – 4a1 – 2b1 – c1 ) + c1

Now let's take a break and find out how many leaf nodes and dual-nodes are present between Level=k and level=k+3

All the nodes at k+3 are leaf nodes
leaf nodes at level k+1 = a1
leaf nodes at level k+2 = b1
so total leaf nodes = 8N1 – 4a1 – 2b1 + a1 + b1
= 8N1 – 3a1 – b1

so Ns = 8N1 – 3a1 – b1

Now lets find out the total number of dual-nodes
level k+3 = 0
level k+2 = 4N1 – 2a1 – b1
level k+1 = 2N1 – a1
level k = N1

so total dual nodes = 7N1 – 3a1 – b1
so Nd = 7N1 – 3a1 – b1

Clearly Ns = Nd + 1

So number of leaf nodes is one greater than number of dual-nodes.

We stopped at level k + 3..... The same logic can be extended to fictitious infinite level binary tree

To Find the a subsequence of number having maximum sum in an array of numbers with positive negative values

Lets know the boundary conditions of the problem first

case 1:
If in negative plane:
conditions :
a. ) If the sum is negative.
keep treack of 2 variables :
1. downfall index ( index at which downfall started from a postive, i.e if the sum is negative )
2. upward index ( index at which upward movement began. i.e just check if the next number is postive )
if upward movement then sum=a[upwardindex]

case 2:
If in positive plane
keep adding as long the sum is positive

Case 3: Analysing transition periods

1. transition from positive plane to negative plane
sum till now of postive plane needs to stored as last_postive_sum

as long we keep moving in the negative plane there is no point in updating this last sum
as it can never increase with negative numbers.

2. But as soon as a trnasition again occurs from negative to positive i.e as sooon as a positive number is found
then new sum is the this found

3. At what time should we compare current_positive_sum and last_positive_sum
a. When a transition occurs from postive plane to negative. i.e when the downindex is freshly updated
then if current_postive_sum > last_positive_sum
then last_positive_Sum = current_positive_sum

4. The whole problem should be analysed by making a graph with y-axis, extending both in neg and posittive directions
values of y-axis are the array values
X-axis is the index of the array



/**
* @author Nitesh
*/
public class MaxSumInArray {

public static int maxSum( int[] in ) {
if ( in.length == 1 ) {
return in[0];
}
int negativeMax = in[0];
boolean notfound = true;
int i = 0;
for ( i = 1; i < in.length; i++ ) {

if ( in[i] < 0 && notfound ) {
if ( in[i] > negativeMax ) negativeMax = in[i];
continue;
}
notfound = false;
break;

}

if ( notfound && in[0] < 0 ) {
System.out.println( "all number are negative. Returning min negative");
return negativeMax;
}
if ( in[0] >= 0 ) {
i = 0;
}
System.out.println("Got the first postitive index :" + i + " , number=" + in[i] );

int current_max = in[i];
int last_max = current_max;
int downfall_index = -1;
int upward_iundex = -1;

for ( int j = i+1; j < in.length ; j++ ) {

/* first check the transition from negative plane to postive plane *
* in that case
* conditions :
* downward_index > -1
* and a[j] > 0
*/
if ( in[j] >= 0 && downfall_index > -1 ) {
downfall_index = -1;
current_max = in[j];
if ( current_max > last_max ) {
last_max = current_max;
}
continue;
}


/*
* If already moving in the negative plane then no need
* to update any pointer, either current_max, last_max, or any index
* condition :
* downward_index > -1
* and
* in[j] < 0
*/
if ( in[j] < 0 && downfall_index > -1 ) {
continue;
}

int t = current_max;
current_max += in[j];

/**
* If in positive plane then just update last max
* and continue
*/
if ( current_max >= 0 ) {
if ( current_max > last_max ) last_max = current_max;
continue;
}


/*
* if transition from positive plane to negative plane, i.e new_sum < 0 ?
*/

assert (current_max < 0 && downfall_index == -1);

if ( current_max < 0 && downfall_index == -1 ) {
downfall_index = j;
// now update last_max, i.e current_max might now be last_max
if ( t > last_max ) last_max = t;

}else {
System.out.println("Something wrong in ALGO ");
}

}

return last_max;
}

public static void main( String[] args ) {
int in[] = { 15,10, -3, -4, -5 }; // 25 ok ... pos, neg

int in1[] = { -3,-1,-22, -3, -4, -5 }; // -1 ok .... only negative

int in2[] = { 10, 13, -4, -6, 22, 1, -17, -19, 2 }; // 36 ok.. pos, neg, pos..

int in3[] = { 6,-11,-10,5 }; // 6 ok... pos, negative plane, positive plane

int max = maxSum( in3 );
System.out.println( "max=" + max );
}

}

Find all the subsets of a given set

public class Subset {


public static List subset( List input ) {
double r = input.size();
int finalsize = (int)Math.pow( 2d, r );
List ret = new ArrayList( finalsize );
int one = 0x0001;
for ( int i = 1; i < finalsize; i++ ) {
int count = 0;
StringBuilder sb = new StringBuilder();
while ( count < finalsize ) {
int k = (i >> count) & one;
if ( k == 1 ) {
sb.append( input.get( count ) ).append(",");
}
count++;

}
ret.add( sb.toString() );
}
return ret;
}

public static void print( List in ) {
int i =1;
for ( String s : in ) {
System.out.println( "count_" + (i++) + " :" + s );
}
}

public static void main( String[] args ) {
List in = new ArrayList();
in.add( "a" );
in.add( "b" );
in.add( "c" );
in.add( "d" );
print ( subset( in) );
}
}

Find permutation of a String or character array

/**
* Finds premutation of an array of characters
* @author Nitesh
*
*/
public class Permutation {

public static void main( String[] args ) {
Permutation perm = new Permutation();
String s = "abcde";
char[] c = s.toCharArray();
char[][] ret = perm.permut( c , 0, c.length-1 );
perm.print( ret );
}


/**
* Begin = begin index
* end = end index
* input = char input
*
* @param input
* @param begin
* @param end
* @return
*/
public char[][] permut( char[] input, int begin, int end ) {

int len = end - begin + 1;
if (len == 1 ) {
char[][] ret = new char[1][];
ret[0] = input;
return ret;
}
if ( len == 2 ) {
char[][] ret = new char[2][];
ret[0] = input;
char[] a = copy( input );
a = swap( a , begin, end );
ret[1] = a;
return ret;
}
char pivot = input[begin];
int pivot_index = begin;
char[][] per = permut( input, begin+1, end );
return merge ( begin, per );

}

char[][] merge( int pivotIndex, char[][] input ) {
int rows = input.length;
int cols = input[0].length - pivotIndex;
int len = rows * cols;
char[][] ret = new char[len][];
for ( int i = 0; i < rows; i++ ) {
ret[i] = input[i];
}
int k = rows;
char[][] cir;
for ( int i = 0; i < rows; i++ ) {
cir = getCir( ret[i], pivotIndex );
for ( int j =0; j < cir.length; j++ ) {
ret[ k++ ] = cir[j];
}
}
return ret;

}

public void print( char[][] c ) {
for ( int i = 0; i< c.length; i ++ ) {
System.out.println( "count_" + (i+1) + "=" + new String( c[i] ) );
}
}

char[][] getCir( char[] c , int ele ) {
char[][] ret = new char[c.length -ele - 1][];

for ( int i = ele + 1, j=0; i < c.length; i++, j++ ) {
char[] cop = copy( c );
cop = swap( cop, ele, i );
ret[j] = cop;
}
return ret;
}

char[] copy( char[] input ) {
char[] ret = new char[ input.length ];
for ( int i = 0; i < input.length; i++ ) {
ret[i] = input[i];
}
return ret;
}

char[] swap( char[] a , int begin, int end ) {
char c = a[begin];
a[begin] = a [end];
a[end] = c;
return a;
}


}

Neko HTML Fragment Parser with Xml Transform

import java.io.ByteArrayInputStream;
import java.io.StringWriter;

import javax.xml.transform.Transformer;
import javax.xml.transform.TransformerException;
import javax.xml.transform.TransformerFactory;
import javax.xml.transform.dom.DOMSource;
import javax.xml.transform.stream.StreamResult;

import org.apache.html.dom.HTMLDocumentImpl;
import org.apache.xpath.XPathAPI;
import org.cyberneko.html.parsers.DOMFragmentParser;
import org.w3c.dom.DocumentFragment;
import org.w3c.dom.Node;
import org.w3c.dom.html.HTMLDocument;
import org.xml.sax.InputSource;

/**
*Working with html fragements and tranforming node result
*to xml string
*/
public class HtmlFragmentTest {

String exp = "//TABLE[@class=\"subscribe_form\"]";
String xml = null;


public HtmlFragmentTest() {

StringBuffer sb = new StringBuffer();

sb.append( "<h2>Contributing to the FAQ</h2>\n" + "<p>If you think that you have a FAQ that's not answered here, or if you\n" + "see something that needs a correction/update, please\n" + "<a href=\"/contribute/\">contribute</a>!</p>\n" );

sb.append( "<table class=\"subscribe_form\" cellpadding=\"0\" cellspacing=\"0\"><tr>\n");

sb.append( "<td class=\"label\">\n" );

sb.append( "To get updates by email whenever the FAQ is updated, enter your email"+ "address here and click "Subscribe:"\n" );

sb.append( "</td>\n" + "<td>\n" + "<form method=\"post\" action=\"/notify.php\">\n" );

sb.append( "<div>\n" + "<input type=\"text\" size=\"20\" name=\"email\" />\n" + "<input type=\"submit\" value=\"Subscribe\" />\n" + "</div>\n" );

sb.append( "</form>\n" + "</td>\n" + "</tr></table>");

xml = sb.toString();

}

public void test() {

HTMLDocument document = new HTMLDocumentImpl();
DocumentFragment doc;
try {

DOMFragmentParser parser = new DOMFragmentParser( );

//parser.setFeature("http://cyberneko.org/html/features/insert-namespaces", true);
parser.setFeature ( "http://xml.org/sax/features/namespaces", false );
parser.setProperty("http://cyberneko.org/html/properties/names/elems", "lower" ); // has no effect, cannot override xerces configuration
parser.setProperty( "http://cyberneko.org/html/properties/names/attrs", "lower" ); // has no effect, cannot override xerces configuration
parser.setFeature("http://cyberneko.org/html/features/balance-tags/document-fragment",true);

doc = document.createDocumentFragment();
InputSource inputSource = new InputSource( new ByteArrayInputStream( xml.getBytes() ) );

parser.parse(inputSource, doc);

Node node = XPathAPI.selectSingleNode(doc, exp);
this.xml = transform( node );
System.out.println( "---------------done once --------------");

} catch(Exception ex) {
ex.printStackTrace();
//return null;
}
}

public static void main( String[] args ) {
HtmlFragmentTest test = new HtmlFragmentTest();
test.test();
test.test();
}

/**
*
* @param node
* @return
* @throws TransformerException
*/
public static String transform( Node node ) throws TransformerException {
StringWriter sw = new StringWriter();
Transformer serializer = TransformerFactory.newInstance().newTransformer();
serializer.transform( new DOMSource( node ), new StreamResult(sw));
String result = sw.toString();
System.out.println( result );
return result;
}

}