One more Print path

A well known problem to the job seekers:

Given a binary tree, print out all of its root-to-leaf paths as defined above. This problem is a little harder than it looks, since the "path so far" needs to be communicated between the recursive calls. Hint: In C, C++, and Java, probably the best solution is to create a recursive helper function printPathsRecur(node, int path[], int pathLen), where the path array communicates the sequence of nodes that led up to the current call. Alternately, the problem may be solved bottom-up, with each node returning its list of paths. This strategy works quite nicely in Lisp, since it can exploit the built in list and mapping primitives. (Thanks to Matthias Felleisen for suggesting this problem.)

Given a binary tree, print out all of its root-to-leaf paths, one per line.

void printPaths(struct node* node) 

Solution you can find easily at : http://cslibrary.stanford.edu/110/BinaryTrees.html

I have not find any new solution till date for this:

I have tried derive new one today (not implemented yet.. )

#include

using namespace std;

printPath(node* root){

string now="";

ppath(root, now); 

}

ppath(node* root, string now){

if(!root) return;

if( root && ! root->left && ! root->right){

print("%s %d\n", now, root->data); return;

}

if(root->left) ppath(root->left, now+'0'+root->data);

if(root->right) ppath(root->right, now+'0'+root->data);

}

Although solution is very simple still like to point out the concept of using string.

string class have following properties:

string+char->string.

and passing string as value to a function will create a new string. 

Please comment the correctness of solution. 

My notes on yoga ..

The blog is about learning I have done today. Aiming towards so that other also can benefited with my learning's.
I am following Baba Ramdev since 2-3 days. I think Yoga and exercise are more & more necessary for software engineers. We guys are not doing any physical work so we are in more critical stage for ..........
Our immunity systems are not good so more.

I am not trying to elaborate any saying or details about yoga. A lot many sites are doing the same in much better way I can do. I am going to post summary(one liners) of steps and time suggested for the daily yoga.
Source I will mention at last. Please do not hesitate googling for much details.

The list of Yoga/ Prayanam, I am able to follow by last watch are:

0) Try to have mild hot water at least in the day. At least have 2 glass of water in the morning.

1) BHASTRIKA PRAYANAM ( Bellow Breath)

How to do: Breath deep to lungs, and relive . Its for expansion & contraction of Lungs. Do it relaxed. Keep the back straight, chin parallel to floor, jaw relaxed.

Precaution: Do with empty stomach. High blood pressure, Ulcer & back pain patient should not do it fast. Pregnant women should not do it.

Time: 2-3 Min, 5 Min max

2) KAPAL BHATI PRAYANAM

How to do: Push air forcefully out. Stomach will itself go in. Force should not to much to sound from mouth. Your body posture should not change.

Precaution: Don't do it with full stomach.

Time: Try to make 30 times in 1 min. Start with 15 min to 30 min.


3) BAHARYA PRAYANAM

How to do: Breath air out as much you can, hold it. Try to move stomach only. Release air out calm.

Precaution: Don't do it with full stomach.

Time: Try to make 5 times . DON'T DO IT TOO MUCH. max 11 times.

4) UDGEETH PRAYANAM

How to do: Breathe in deeply, and chant 'Om'kar. OOOOOOm ( long O and small m )

Precaution:

Time: 10 Min or more according to time


5) ANULOM VILOM PRAYANAM

How to do: Breath air in from one of the nasal (like left), close other with thumb or finger. Release air from other nasal(like right) with closing the first nasal using finger or thumb. Do same for the this nasal.

Precaution:

Time: At least 10 minutes, do up to 20 minutes. (250 to 500 times a day)

6) BHRAMRI PRAYANAM

How to do: Close ears with thumb, index finger on forehead, and rest three on base of nose touching eyes. Breathe in. And now breathe out through nose while humming like a bee. Try to say OM.............. Try to release air as slow as you can.

Precaution:

Time: Up to 5 - 7 Times

7) UJJAYI PRAYANAM

How to do: Inhale, slowly drawing air by both the nostrils in such a way that while inhaling the touch of air is experienced in the throat and some sound is produced. Breath out slowly without sound form one of the nassal one by one.

Precaution:

Time: Up to 15 - 20 Times


Its karma time now.
Do it.


Daily 7 are over now.
I will update as soon as I will learn new.

hadPathSum - Tree Problem

I have found one problem at : http://cslibrary.stanford.edu/110/BinaryTrees.html

hasPathSum()

----------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------
We'll define a "root-to-leaf path" to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf (a node with no children). We'll say that an empty tree contains no root-to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths:

5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1

Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1

For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.

Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found. (Thanks to Owen Astrachan for suggesting this problem.)

int hasPathSum(struct node* node, int sum);

----------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------

After solving this when I matched the solution, I disagree with the provided solution. It will calculate 5- 8- 4 as path.
Provided solution is:

int hasPathSum(struct node* node, int sum) {
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}

Here it is not calculating tree leaf properly.

I have write following code.

bool hasPathSum(TNodeRef root, int data){
if(!root) return (false); // Will come to this when node have only right or left node (mean not leaf)
if(root->left == NULL && root->right == NULL) return data == root->data;
data -=root->data;
return( hasPathSum(root->left, data)||
hasPathSum(root->right, data));
}

Please comment if this too have mistake.

:)