Locate a leaf and rob a road

Shortest path to a leaf

We are given a binary tree with a 'ragged' bottom and aske to find the length of the shortest path from the root to a leaf.

If you number the nodes, left to right from 0, at any given level in a binary tree, then the children of node number n at level d are at nodes numbers 2n and 2n+1 in level d+1.  

So for example, at level 2 there are 4 nodes, and at level 3 there are 8.  The children of node 3 (counting again from 0) in level 2 are at nodes 6 and 7 of level 3.

My first thought was simply to look for the first level where the number of occupied nodes was not 2**level, but that doesn't work where there are nodes with only one child, as in the second example.

My solution is therefore to examine each level, starting at zero, and check that every node has at least one child, using the above algorithm. If not, this level's depth is the desired answer.

Efficient robbery

The first thing to ask is: how do I know the amount of swag in each house before I start? Lack of that knowledge means that any solution to the task is unlikely to be helpful to a real robber, which is a relief.

My relatively simple solution was to write a recursive function, robberies, which takes as arguments a starting house number and the amount of swag already in my bag, and checks each of the individual houses that I could rob next - ie the next but one and all the rest up to the end of the street. It then recurses for each of these until the last house is reached.

This is fine for a short street, but the effort increases order n**2 as the street length increases, and on my little computer a street longer than about 35 houses took longer than I fancied waiting.

How could one make a more efficient algorithm? For example, as the algorithm knows the best solution found to date, it could give up on the recursion if the swag to date plus the most I could collect from all the remaining houses is less than the best result already found.  

I though too about ordering the houses by value, but given, say, the three most valuable - say they are numbers 14, 22 and 31 - determining which paths include these three is non-trivial, and it could still be the case that a combination not including all of these three was the most lucrative.

So I look forward to see what the team comes up with!