The trees that we're working with don't have a fixed size; there is no minimum or maximum branch length. It's perfectly possible for one branch to be four nodes in length and another twelve nodes. We've thought about using the non decision nodes (ie where something gets input like a name or bank account number rather than the user deciding on something) but there aren't that many of those. Certainly not enough to stop a 0% or 100% scenario.
I've had a quick crawl of the web but can't find anything. I think the right way to go might be a 'worst case' approach whereby the script looks at the total possible number of nodes left and uses this as a basis to work out a percentage. This should be easy enough to implement with an xml parser.