I am solving an algorithm question:

You are given a binary tree root. In one operation you can delete one leaf node in the tree. Return the number of different ways there are to delete the whole tree. So, if the tree is:

    1
  /  \
 2     3
     /
    4

The expected answer is 3: [2, 4, 3, 1],[4, 2, 3, 1] and [4, 3, 2, 1].

I have been thinking hard, but I don't know how to formulate the recursive function. Thinking along the lines of the Climbing Stairs problem in which we count "distinct ways can you climb to the top", I think I have to use DP, but I am unable to formulate the recursive relation.

If you could provide some hints/guidance, I would appreciate it. Thanks!

Edit: Given the following tree:

    1
  /  \
 2     3
     /   \
    4     5

There are 2 ways in which we could delete the children of 3 (4, 5); but how to use this info to determine the number of ways for root node 1? (The expected answer is 8).

CodePudding user response：

For a give node X, we want to know u(X) - the number of unique delete sequences.

Assume this node has two children A, B with sizes |A|, |B| and known u(A) and u(B).

How many delete sequences can you construct for X? You could take any two sequences from u(A) and u(B) and root and combine them together. The result will be a valid delete sequence for X if the following holds:

• The root X must be deleted last.
• Order of deletion of any two nodes from different subtrees is arbitrary.
• Order of deletion of any two nodes from the same subtree is fixed given its chosen delete sequence.

This means you want to find out the number of ways you can interleave both sequences (and append X).

Notice that the length of a delete sequence is the size of the tree, that's kind of trivial if you think about it.

Also give some though to the fact that this way we can generate all the delete sequences for X, that might not be so trivial.

So if I'm counting correctly, the formula you are looking for is u(X)= [|A| |B| choose |A|] * u(A) * u(B).

It holds for empty children too if we define u(empty)=1.

Just be careful about overflow, the number of combinations will explode quite quickly.