1

This is a homework, I have difficulties in thinking of it. Please give me some ideas on recursions and DP solutions. Thanks a lot

generate and print all structurally distinct full binary trees with n leaves in dotted parentheses form， "full" means all internal (non-leaf) nodes have exactly two children.

For example, there are 5 distinct full binary trees with 4 leaves each.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
lxx22
  • 225
  • 7
  • 17
  • Please say what you have tried already, and what websites or other documentation you have read to try to understand the issue. – Alex Brown Sep 06 '12 at 03:31
  • Clarification please. Do the leaf-bearing nodes have to sprout exactly two leaves? If so then n must be even. Can you give an example of what your teacher means by dotted parentheses form? – Jive Dadson Sep 06 '12 at 03:33
  • There are a number of definitions of a "full tree," but this is not any of them. A more usual definition is that all leaves are within one level of each other. According to your definition, a tree with all the left nodes as leaves and all the right nodes as non-leaves (except the last one) would be considered "full"... – BlueRaja - Danny Pflughoeft Sep 06 '12 at 03:52
  • When generating the possibilities for four leaves, think about the possibilities for three leaves. Can you use the list of possibilities for three leaves to help you do four? – Vaughn Cato Sep 06 '12 at 03:57
  • Sorry not to make the question clear. "Full" means here an internal code has to have two children, and there is no need to be the same level for all the leaves. – lxx22 Sep 06 '12 at 15:18
  • To Vaughn, yes, DP is a good way of thinking, I have to include the number of the lowest level leaves. – lxx22 Sep 06 '12 at 15:26

4 Answers4

3

In Python you could do this

def gendistinct(n):
    leafnode = '(.)'
    dp = []
    newset = set()
    newset.add(leafnode)
    dp.append(newset)
    for i in range(1,n):
        newset = set()
        for j in range(i):
            for leftchild in dp[j]:
                for rightchild in dp[i-j-1]:
                    newset.add('(' + '.' + leftchild + rightchild + ')')
        dp.append(newset)
    return dp[-1]

alltrees = gendistinct(4)
for tree in alltrees:
    print tree
yzernik
  • 1,161
  • 2
  • 13
  • 19
  • I like this solution... it's fast and doesn't eat too much memory since the lists all reference lists from previous iterations. Though, this doesn't work for n=0 like the solution I posted does – eric.frederich Jan 12 '17 at 15:49
2

Another Python example with a different strategy.

This is recursive and uses generators. It is slower than the other implementation here but should use less memory since only one list should ever exist in memory at a time.

#!/usr/bin/env python

import itertools

def all_possible_trees(n):
    if n == 1:
        yield 'l'
    for split in range(1, n):
        gen_left = all_possible_trees(split)
        gen_right = all_possible_trees(n-split)
        for left, right in itertools.product(gen_left, gen_right):
            yield [left, right]

if __name__ == '__main__':
    import sys
    n = int(sys.argv[1])
    for thing in all_possible_trees(n):
        print(thing)
eric.frederich
  • 1,598
  • 4
  • 17
  • 30
  • +1 This is a nice simple generator-based solution. It even generates the trees in a nice order that makes sense. – Ole Thomsen Buus Apr 19 '17 at 16:58
  • Thanks ;-) The problem itself is simple, so it's nice when it can be expressed in a simple way too (hooray Python). If it weren't for the recursion it could be expressed as a generator comprehension – eric.frederich May 04 '17 at 14:47
1

I don't see an obvious way to do it with recursion, but no doubt there is one.

Rather, I would try a dynamic programming approach.

Note that under your definition of full tree, a tree with n leaves has n-1 internal nodes. Also note that the trees can be generated from smaller trees by joining together at the root two trees with sizes 1 to n-1 leaves on the left with n-1 to 1 leaves on the right.

Note also that the "trees" of various sizes can be stored as dotted parenthesis strings. To build a new tree from these, concatenate ( Left , Right ).

So start with the single tree with 1 leaf (that is, a single node). Build the lists of trees of increasing size up to n. To build the list of k-leaf trees, for each j = 1 to k-1, for each tree of j leaves, for each tree of k-j leaves, concatenate to build the tree (with k leaves) and add to the list.

As you build the n-leaf trees, you can print them out rather than store them.

There are 5*1 + 2*1 + 1*2 + 1*5 = 14 trees with 5 leaves.

There are 14*1 + 5*1 + 2*2 + 1*5 + 1*14 = 42 trees with 6 leaves.

UncleO
  • 8,299
  • 21
  • 29
0

U can use recursion, on i-th step u consider i-th level of tree and u chose which nodes will be present on this level according to constraints: - there is parent on previous level - no single children present (by your definition of "full" tree)

recursion ends when u have exactly N nodes.

Herokiller
  • 2,891
  • 5
  • 32
  • 50
  • I do not quite get what you said. Would you please walk me through more in detail? Thanks a lot! – lxx22 Sep 06 '12 at 20:40