#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.

We reviewed relabel-to-front algorithm next. This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.  We saw what admissible edges are. If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may cause the edge u,v to become admissible. The admissible edges also applies to relabel operation

The discharge operation proceeds like this :

While there is a neighbor to u, apply the following operations. Set v to the current neighbor. If v is nil, apply the relabel operation to u. Reset the current to the head of the new neighbor list. If v is not nil and the capacity of preflow from u to v is greater than zero and the height of u is one level greater than that of v, apply the push operation on (u,v). If neither relabel nor push occurs, skip to the next neighbor.

The Relabel to front algorithm proceeds on a flow network G with source s and sink t this way. We initialize the preflow in the network. We choose a set of all vertices in G excluding the source and sink and in arbiyrary order. For each vertex in this set, We set its current to head. We start with the head of the set L as u. While u is not nil, we peform the following operations. We remember the old height of u. Then we appy the diacharge method to u. If the height of u is greater than the old height, we move u to the front of list L. We choose the next u.

#codingexercise

Given a binary tree, defining a term “complete path sum” as, sum of values of nodes lying in a path from root to the leaf; Now given a value ‘k’, we have to find the k-light  path and prune the binary tree i.e. prune/delete nodes for which complete path sum is greater than k.

node PruneKLight(Node root, int K, ref int sum)

{

if (root== null) return;

sum += root.data;

root.left= PruneKLight(root.left, K, ref sum);

root.right = PruneKLight(root.right, K, ref sum);

if (root.left == null && root.right == null) 

{

if (sum > k ){

Sum -= root.data;

delete root;

root = null;

Return root;

}

}

sum-=root.data;

return root;

}

Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that node.
void ToGreater(Node root, ref int sum)
{
if (root == null) return;
// reverse inorder
ToGreater(root.right, ref int sum);
sum += root.data;
root.data = sum-root.data;
ToGreater(root.left, ref int sum);
}

Given a BST, transform it into lesser sum tree where each node contains sum of all nodes lesser than that node.
void ToLesser(Node root, ref int sum)
{
if (root == null) return;
ToLesser(root.left, ref int sum);
Var val = root.data;
Root.data = sum;
sum += val;
ToLesser(root.right, ref int sum);
}