#algorithm discussion continued
Today we continue reading the flow networks. We were looking at maximum flows

Maximum flows can also be calculated using "push-relabel" method.

This method performs two basic operations: pushing flow excess from a vertex to one of its neighbors and relabeling a vertex.

The Push operation applies only if u is an overflowing vertex, cf(u,v) > 0 and h(u) = h(v) + 1. The push operation updates the preflow f and the excess flows for u and v. It assumes that we can compute residual capacity in constant time given c and f.

All the flow is downward  in the flow network so all the residual edges are at the same level, one level down or upwards. we discussed the following lemmas

1) An overflowing vertex can be either pushed or relabeled.

2) Vertex heights never decrease

3) The execution of the generic-push-relabel method on G maintains the attribute h as a height function.

Another lemma that gives ank important property on the height function states that 

 If f is a preflow in the flow network G, then there is no path from source to sink through the residual network Gf.

If we assumed the reverse and said that there is a path source s, v0, v1, ... ,vk, sink t where k is less than the total number of vertices n, then we know h(vi) <= h(vi+1) +1 and combining them successively we get h(s) <= h(t) + k. We already know that h(t) = 0 and k < n, so h(s) <= k < n which contradicts the invariant that h(s) = n

With the above lemmas we prove the generic push relabel algorithm as follows :
The intialization step creates a preflow.
The progress of the algorithm maintains the preflow.
At termination, there are no overflowing vertices and this preflow is a valid flow and there is no path in the residual network. Consequently, the flow is maximum.

#codingexercise

Void getcount(node head,  ref int count)

{

If (head == null) return;

getcount(head.next, ref count);

Count += 1;

}

Bool islessthanEqualTo(node tree1, node tree2)
{
if (tree1 == null && tree2 == null) return true;
if (tree1 == null || tree2 == null) return false:
if(tree1.data > tree2.data) return false;
Return islessthanEqualto(tree1.left, tree2.left) && islessthanEqualTo(tree1.right, tree2.right);
}

How many binary search trees are possible from a sequence of n numbers ?

The nunber of binary search trees is the nth Catalan number.
1/(n+1) 2n C n
= (2n)!/ (n+1)!n!