count odd numbers of an N-ary tree

user_9563427 0
Viewed 47

I am struggling with this exercise. It tells me to count all odd numbers present in an N-Ary. The exercise demands me to use recursion

Take a look at the following tree

              5                                           
      ________|_____________                        
     |          |           |                     
     20         4           6                     
     |     _____|______                      
     11   |   |  |  |  |                    
          10  2  9  8  7                  
            __|__                        
           |     |                    
           3     1

There are 12 numbers in it. Among these numers, 6 of them are odd which is the output i am looking for. However, the code i have written doesn't solve the issue and i don't understand why.

The function i have implemented returns 0 which is incorrect.

def es7(tree):
    n = 0
    for element in tree.f: 
        n = es7(element)
        if element.id % 2 == 1: 
            n += 1 
    return n  
 

class Nodo:
    def __init__(self,V):
        self.id=V
        self.f=[]


################### DA QUI IN GIÙ SONO SOLO FUNZIONI NECESSARIE PER I TEST #####################

def fromLista(lista):
    '''Crea l'albero da una lista [valore, listafigli]
           In cui lista figli contiene alberi o e' la lista vuota. '''
    r=Nodo(lista[0])
    r.f=[fromLista(x) for x in lista[1]]
    return r

def toLista(nodo):
    ''' Converte l'albero in una lista di liste [valore, listafigli]'''
    return [nodo.id, [toLista(x) for x in nodo.f]]

Any suggestions?

Thanks

python
2 Answers

One simple approach to this problem; is to simply to do a level order traversal of the N-ary tree.

Consider the following iterative solutions, which can give some insights into writing your recursive solution.

To re-write your code, I would do something on these lines.
Consider this snippet below:

def es7(tree):
    q, level = [tree], []
    while any(q):
        level.append([node.id for node in q])
        q = [child for node in q for child in node.f if child]

    ans = 0
    for l in level:
        for num in l:
            if num & 1:
                ans += num
    return ans

Consider the snippet of code below: (Non-recursive Solution)

from collections import deque

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return 
        
        q = deque([root])
        level = 0
        result = []
        
        while q:
            result.append([])
            for i in range(len(q)):
                node = q.popleft()
                result[level].append(node.val)
                
                for c in node.children:
                    q.append(c)
            
            level += 1
        
        return result

In the above code, result will have all the elements of the n-ary tree according to levels. Parse through list, and add all the odd numbers.

That would be something along these lines:-

for level in result:
    for num in result:
        if num & 1:
           ans += num

Alternatively you could also add-up all the odd-numbers as you are traversing the tree.

user_35553660

You are shadowing n at each iteration. What you probably want to do is something like

def es7(tree):
    n = 0
    for element in tree.f: 
        n += es7(element) # <-- note the `+=`
        if element.id % 2 == 1: 
            n += 1 
    return n

However, I think this code is still not completely sound (depending on your representation of a tree), which you might realize on a tree with a single, odd number.

user_59562610
Related