Given postorder of a binary tree and a nodepath.find in how many root-to-leaf paths does the nodepath lie.
If postorder traversal is txyCabDBA small letters are leaf nodes and capital are root or intermediate nodes.find if AD lie in how many paths.
Please give me an answer.its urgent.
First of all ur input test case is wrong because three leaves cannot get printed without an intermediate node getting printed.
You basically have to calculate the number of leaves below the node x in the path ux(path from u to x).
You can easily construct the tree from the information.
My solution will be the following given it is a binary tree for case txCabDBA
t,x can have parent in C and a,b can have parent in D.
replace string as cdDBA
cd have parent in D.
replace string as dBA.
so the tree can be constructed .rest is trivial.
The tree inorder is
A
t B
C D
x y a b