How to calculate width of tree recursively?

Question

I have a tree with data structure:

root: {
    children:[
        {children: [
            {children:[]}
        ]},
        {children: []}
    ]
}

Here is example of tree where the result should be 4(maximum width)

I can't imagine doing it without recursion. Have a `counter = defaultdict(int)`, and as you recurse down the tree, keep track of your depth and do counter[depth] += 1. Then when you're done, `max(counter.values())`. — Frank Yellin, Oct 21 '22 at 06:08
you should go with `level order traversal` where you will be maintaining level wise queue, you can check the max(len(queue)) and you will get the max_width — Deepak Tripathi, Oct 21 '22 at 06:44

blhsing · Answer 1 · 2022-10-21T08:42:22.927

To do this with recursion, you can make a helper function that returns the size of the current level and then the sums of sizes of children at each level as a sequence. Take the maximum of sizes from the sequence for output:

from itertools import zip_longest

def max_tree_width(tree):
    def widths(tree):
        return len(tree), *map(sum, zip_longest(*map(widths, tree.values()), fillvalue=0))
    return max(widths(tree))

So that given the following input, adapted from the sample tree in your question:

tree = {
    'R': {
        'A': {
            'C': {},
            'D': {
                'G': {}
            }
        },
        'B': {
            'E': {},
            'F': {}
        },
        'X': {}
    }
}

max_tree_width(tree) would return: 4

Demo: https://replit.com/@blhsing/CarelessPutridAutocad

score 1 · Answer 2 · answered Oct 21 '22 at 11:57

This can of course be solved in several ways. But here is a variant that uses tail recursion:

def width_calc(trees, maxwidth=0):                                             
    # trees should be a list of all subtrees at the current level, so if its a 
    # dict (as expected in the first call) it is wrapped in a list.            
    if type(trees) is dict:                                                    
        trees = [trees]                                                        
    # Get all subtrees at the current level                                    
    subtrees = [v for tree in trees for v in tree.values()]                    
    # If there is subtrees at the current level then recurse down one more     
    # level. Also calculate the maxwidth so far and send to the next level.    
    if subtrees:                                                               
        return width_calc(subtrees, max(maxwidth, len(subtrees)))              
    # There is no subtrees at this level so we reached the last leaves and the 
    # maxwith can be returned.                                                 
    return maxwidth

Using your tree data (implemented by @blhsing in another anser), the call width_calc(tree) would return 4.

How to calculate width of tree recursively?

2 Answers2