Check how many nodes in a B-Tree are size n

Question

Given a B-Tree, I have to look for all the nodes that are length n. However, I'm struggling to traverse with B-trees of a height greater than 1. I'm not sure how I can make my recursive call or my loop move such that I can reach the nodes at a lower level.

This is my code:

def nodes_with_n_items(T,n):
    L = []
    if len(T.data) == n:
        L.append(T)
    if len(T.child) == 0:
        return L
    
    for item in T.child:
        if len(item.data) == n:
            L.append(item)
        L + nodes_with_n_items(item, n)

    return L

This is my expected output:

There are 1 nodes with 1 items
[11]
There are 4 nodes with 2 items
[2, 6]
[0, 1]
[12, 13]
[15, 16]
There are 3 nodes with 3 items
[3, 4, 5]
[14, 17, 21]
[18, 19, 20]
There are 2 nodes with 4 items
[7, 8, 9, 10]
[22, 23, 24, 25]
There are 0 nodes with 5 items

This is my output:

There are 1 nodes with 1 items
[11]
There are 1 nodes with 2 items
[2, 6]
There are 1 nodes with 3 items
[14, 17, 21]
There are 0 nodes with 4 items
There are 0 nodes with 5 items

My class that cannot be changed:

def __init__(self,  max_items = 5):
        self.data = []
        self.child = []
        self.max_items = max_items

This is my main:

    print('\nQuestion 4')
    for i,T in enumerate(btree_list):
        name = 'btree_list[{}]'.format(i)
        print('\nT =',name)
        for n in range(1,6):
            #print('nodes_with_n_items(T,{}):'.format(n),end =' ')
            N = nodes_with_n_items(T,n)
            print('There are {} nodes with {} items'.format(len(N),n))
            for t in N:
                print(t.data)

Answer 1

The issues are in the for loop:

• L + nodes_with_n_items(item, n) correctly makes a recursive call, and the + combines L and that result from recursion into a new list, however that new list is going nowhere; L is not extended. To extend L, you could use += instead of +.

• L.append(item) should not appear in that for loop, because that will be taken care of in the recursive call. The loop should only make the recursive call and add that result to L.

Not a problem, but you don't really need to have the if len(T.child) == 0: case treated separately. You can drop that if block. If there are no children, the loop will not make any iterations which is exactly what you want in that case.

So the corrected code becomes:

def nodes_with_n_items(T, n):
    L = []
    if len(T.data) == n:
        L.append(T)
    for item in T.child:
        L += nodes_with_n_items(item, n)
    return L

This will give the desired output.

Alternative

You may want to consider defining a generator instead, and in the main program build the list from the generated tree nodes:

def nodes_with_n_items(T, n):
    if len(T.data) == n:
        yield T
    for item in T.child:
        yield from nodes_with_n_items(item, n)

And in your main code, replace

N = nodes_with_n_items(T, n)

with

N = list(nodes_with_n_items(T, n))