On determining the maximum depth of an arbitrary nested list

Question

I am currently working with a recursive function in Python, and I came across it. As stated, the problem is returning the maximum depth of an arbitrary nested list.

Here is what I still have:

def depthCount(lst): 'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.' var = 0 if len(lst) > 0: if type(lst[0]) == list: var += 1 depthCount(lst[1:]) else: depthCount(lst[1:]) else: return var 

I feel the problem is with my recursive calls (this may be obvious). It really will return var when the list reaches the end, but when I have a non-empty list, everything goes wrong. Nothing returns at all.

Am I going to draw wrong? Do I have to do something before a slice in a recursive call?

The problem may also be related to my base case.

Answer 1

If they are only nested lists , for example [[[], []], [], [[]]] , here is a good solution:

 def depthCount(lst): return 1 + max(map(depthCount, lst), default=0) 

Here is a small variation that you could use if you are not using Python 3.4, where the default argument was entered:

 def depthCount(lst): return len(lst) and 1 + max(map(depthCount, lst)) 

They also differ in how they calculate. The first one considers the empty list to be depth 1, the second one to depth 0. The first one is easily adaptable, but just set it to -1 by default.

---

If they are not just nested lists , for example, [[[1], 'a', [-5.5]], [(6,3)], [['hi']]]) , here is an adaptation to this:

 def depthCount(x): return 1 + max(map(depthCount, x)) if x and isinstance(x, list) else 0 def depthCount(x): return int(isinstance(x, list)) and len(x) and 1 + max(map(depthCount, x)) 

Make sure you understand how the latter works. If you don't already know this, this will teach you how and works in Python :-)

---

Performing a "purely recursive" task:

 def depthCount(x, depth=0): if not x or not isinstance(x, list): return depth return max(depthCount(x[0], depth+1), depthCount(x[1:], depth)) 

Of course, the extra argument is a little ugly, but I think this is normal.

Answer 2

It really will return var when the list reaches the end, but when I have a non-empty list, everything goes wrong. Nothing returns at all.

This is because you do not have a return , except for the base argument else for an empty list. And if you fall from the end of the function without pressing return , that means the function returns None .

But you have one more problem. You start var = 0 and then maybe do var += 1 ... but you don't pass this down to recursive calls or use any result from recursive calls. Thus, recursive calls have no useful effect.

What you probably meant is something like this:

 def depthCount(lst): 'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.' if len(lst) > 0: if type(lst[0]) == list: return 1 + depthCount(lst[1:]) else: return depthCount(lst[1:]) else: return 0 

But this is still not really the case. The amount of list depth is 1 greater than the number of depths of its deepest element. Just checking its second element will not do you any good; you need to check everything. So what you really want is something like this:

 def depthCount(lst): 'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.' if isinstance(lst, list): return 1 + max(depthCount(x) for x in lst) else: return 0 

---

If you want to replace this iterative for x in lst with a second level of recursion, of course you can, but I see no good reason for this; it just makes the code more complex for no reason. For instance:

 def max_child_count(lst): if lst: return max(depth_count(lst[0]), max_child_count(lst[1:])) else: return 0 def depth_count(lst): if isinstance(lst, list): return 1 + max_child_count(lst) else: return 0 

---

This may not be so. This definitely does the right thing, for example, [1, [2,3], [4, [5]]] . But what to do, say, [] ? I can not say on your question. If it should return 0 or 1 , you obviously need to change the if accordingly. If this is illegal entry, then he is already doing the right thing. (And this should also answer the question of what it should do for, for example, [[[], []], [], [[]]] , but be sure to think about this case.)

Answer 3

So the data structure you are referring to is a k-ary tree, also known as an n-ary tree, with arbitrary branching. Here is the code for determining max. depth of n-ary tree with arbitrary branching.

 def maxdepth(tree): if isleaf(tree): return 1 maximum = 0 for child in children(tree): depth = maxdepth(child) if depth > maximum: maximum = depth return maximum + 1 

You can see the code in action with various test inputs here .