CODEWITHSUNDEEP
algorithmrecursiontree
Andrew
Andrew

Reputation: 117

How to calculate the number of leafs with n leafs?

Let's say I have a tree where each node can have anywhere from 0-3 leafs.

I want to go through the tree, and return a tuple (a, b, c) where a = nodes with 1 leaf, b = nodes with 2 leafs, and c = nodes with 3 leafs.

My general code is recursive, and looks like this:

treeNode(tree, (a, b, c)) =
  if tree = Empty
    return (a, b, c)
  else if tree = Node(n1, n2, n3)
    if n1 = tree and n2 = tree and n3 = tree
      treeNode(n1, (a, b, c + 3)) + treeNode(n2, (a, b, c + 3)) + treeNode(n3, (a, b, c + 3))
    else if ...

At that point, I don't know how to go on. I'm stuck on two parts.

a) How can I call the recursive function three times without there being an overlap? I'm guessing adding 1/3 instead of 3 and 1/2 instead of 2 when there are two nodes?

b) How can I eventually add them all together? I get three separate tuples of (a, b, c) for everytime there are three nodes, two tuples for two nodes and so on. I can't use temporary variables in SML, so I can't seem to get around it.

Any ideas on the best way to do this function? I'm trying to stick to recursion and I thought of calling different functions when there are different number of nodes, but that means traversing the tree more than once and I don't want it to be inefficient.

Upvotes: 1

Views: 84

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Something along these lines?

Pseudocode:

# returns triple (a,b,c) of counts of nodes with 1,2 and 3 subtrees
f(T):
  result = (0,0,0)

  if T.nodes.length == 0:
    return result

  for node in T.nodes:
    combine result with f(node)

  result[ T.nodes.length ] += 1

  return result

Example:

         Node # returns answer (0,1,1) + 1 in position a = (1,1,1)
        /
       Node   # returns (0,0,0) + (0,0,1) + 1 in position b
      /    \
    Node    Node  # return (0,0,0) and (0,0,1)
           / | \
          N  N  N  # each return (0,0,0)

Upvotes: 2

Related Questions