Find the depth of an N-ary Tree

Question

I'm trying to find the depth of a n-ary tree.

I start by noticing that this problem is ripe for recursion because everytime I recurse on a child, I still retain the same n-ary tree structure. Since I'm looking for depth DFS would also come in handy. Here' is my attempt

def maxDepth(self, root: 'Node') -> int:
    if not root:
        return 0

    self.depths = []

    def dfs(node):
        if not node:
            return 0
        else:
            if not node.children:
                return 1
            for child in node.children:
                d = 1 + dfs(child)
                self.depths.append(d)

    dfs(root)
    return max(self.depths)

My dfs implementation is done recursively. Everytime we recurse into a deeper level we add 1 to the depth d. Otherwise, we return 1 if no children or 0 if it's a null node.

Since I'm keeping track of the depths in a global variable, all I have to do is then return the maximum of the list.

However, I'm getting an error at d = 1 + dfs(child), it's telling me that it's attempting to perform a 'int' + 'Nonetype' ...

I could return d inside the for loop, but then I would be prematurely exiting the dfs before I finished going through node.children...

Any advice? Oh, and tips with recursion would be greatly appreciated :)

score 2 · Answer 1 · answered Jul 25 '20 at 02:58

To make a recursive function work, you need to always return a value from it.

def max_depth(node: Node) -> int:
    if not node.children:
        return 1
    return 1 + max(max_depth(child) for child in node.children)

In the above recursive function (which is a DFS), we return 1 if the node has no children, and if not return 1 plus the maximum depth among all its children. At the very bottom of the tree (the leaf nodes), the return 1 case is triggered; at all other nodes, we build a sum recursively.

Find the depth of an N-ary Tree

1 Answers1