Determine number of leaf nodes in tree vs. non-leaf nodes

user_1763652 0
Viewed 465

I have a dictionary which contains subdictionaries. It's a decision tree with nodes, some leaf nodes and some non-leaf nodes. How can I count each of these given the dictionary?

For example:

{'Outlook': {'Overcast': 'Yes', 'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}}, 'Sunny': {'Humidity': {'High': 'No', 'Normal': 'Yes'}}}}

This generates a tree like below:

enter image description here

In it are three non-leaf nodes and five leaf nodes. I have a general idea of how I can do it:

def count(d):
  a, b = 0, 0 # non-leaf nodes and leaf nodes
  for key, value in d.items():
    if isinstance(value, dict):
      a += 1
      # some recursive call on value
    else:
      b+= 1
  return a, b

But I'm not sure how to organize the recursive call. Is there a built-in method?

decision-tree tree dictionary python
3 Answers

You can do simply

def count(d):
  a, b = 0, 0 # subdicts and not-subdicts
  for key, value in d.items():
    if isinstance(value, dict):
      a += 1
      suba, subb = count(value)
      a += suba
      b += subb
    else:
      b += 1
  return a, b

However, your example has five "non-dictionaries" and five "dictionaries."

user_35993700

This is what you are looking for:

def get_count(d, c = {0:0, 1:0}):
    c[0]+=1    #count non-leaf nodes
    nodes = d.keys()
    for node in nodes:
      subnodes = d[node].values()
      for subnode in subnodes:
          if isinstance(subnode, dict)           
              get_count(subnode,c)
          else:
              c[1]+=1  #count leaf nodes

    return c




d = {'Outlook': {'Overcast': 'Yes', 'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}}, 'Sunny': {'Humidity': {'High': 'No', 'Normal': 'Yes'}}}}

print(get_count(d))

Output : 3,5

3 : no of non-leaf nodes

5 : no. of leaf nodes

user_67644430

A possibility is to create a running dictionary that stores the counts:

def get_count(d, c):
  for a, b in d.items():
    c[isinstance(b, dict)] += 1
    if isinstance(b, dict):
       get_count(b, c)


d = {'Outlook': {'Overcast': 'Yes', 'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}}, 'Sunny': {'Humidity': {'High': 'No', 'Normal': 'Yes'}}}}
c = {0:0, 1:0}
get_count(d, c)
print(c)

Output:

{0: 5, 1: 5}
#0: elements, #1: sub-dictionaries
user_73267380
Related