1

I'm trying to write code that returns the depth of the deepest leaf in a tree with arbitrary number of children per nodes, in Python, using DFS rather than BFS. It seeems I'm close, but the following code still has some bug that I can't figure out (i.e. the returned depth is not correct). Any help?

A test tree would be simply: [[1,2,3],[4,5],[6],[7],[8],[],[],[],[]]

def max_depth_dfs(tree): # DOESN'T WORK

    max_depth, curr_depth, Q = 0,0, [0]
    visited = set()

    while Q != []:
        n = Q[0]
        more = [v for v in tree[n] if v not in visited]
        if not more:
            visited.add(n)
            curr_depth -= 1
            Q = Q[1:]
        else:
            curr_depth += 1

        max_depth = max(max_depth, curr_depth)
        Q = more + Q

    return max_depth
Improve this question
10
  • Just to make sure the issue is in the code and the interpretation of the requirement: What would you expect the depth to be in your example tree of [[1,2,3],[4,5],[6],[7],[8],[],[],[],[]]? And what is the code returning? Commented May 18, 2012 at 20:44
  • Yes, good point. I'm expecting the depth of node 0 to be 0, and the depth of that specific tree to be 3. The depth of [[1],[]] should be 1, the depth of [[1],[2],[]] should be 2 and so on. Commented May 18, 2012 at 20:45
  • 1
    For that input, this does return 3 Repl.it proof Commented May 18, 2012 at 20:47
  • You are right, but it's a lucky case. [[1,2,3],[4,5],[6],[7],[],[],[8],[],[]] gives 2, and it should be 3. I was tracing "curr_depth" on the first example, and although it gives 3, curr_depth was out of whack. Commented May 18, 2012 at 20:49
  • I'm a bit confused by the tree structure. Is it that an integer a leaf node with a data value, and an array is a branch node? None of your examples show further nesting like [[1] [2 [3, 4]]]. Is that allowed? Commented May 18, 2012 at 20:55

4 Answers 4

Reset to default
1

I found the bug!

if not more:
    visited.add(n)
    curr_depth -= 1
    Q = Q[1:]

When you visit the node 4, curr_depth is equal to 2. Node 4 has no children, so you decrease the curr_depth and curr_depth is equal to 1 now. However, the next node you will visit is node 5 and the depth of node 5 is 2 instead of 1. Therefore, curr_depth doesn't record the correct depth of the node in the tree.

The following solution may be helpful.

def max_depth_dfs(tree):

    max_depth, curr_depth, Q = 0, 0, [0]
    visited = set()

    while Q != []:
        n = Q[0]

        max_depth = max(max_depth, curr_depth)

        if n in visited:
            curr_depth -= 1
            Q = Q[1:]
            continue

        #print n, curr_depth     #show the node and its depth in the tree

        visited.add(n)
        more = [v for v in tree[n]]
        if not more:
            Q = Q[1:]
        else:
            curr_depth += 1
            Q = more + Q

    return max_depth
Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

One thing I realized is that keeping the "visited" data structure means that we are "copying" the tree to that data structure. That is, at the end of the execution, all the nodes are stored once in "tree" and once in "visited"... Is it possible to do better?
You can just record the index of the node which is visited, instead of copying the node to "visited" data structure.
Yes, not copy the whole node itself. I was thinking more about not having the "visited" data structure at all, neither for whole nodes, nor for references to nodes.
Recursive version can do that, but I don't think it's a good idea.
I'm wondering if we cannot leverage the way DFS progresses through the tree to "know" directly which nodes have been visited. Plus, when you are somewhere on the "right" of the tree, you don't need to remember which nodes you visited on the "left" (because DFS will never go back there). In fact, for example, each time you get back to the root, you can purge "visited" (and reduce memory usage). Is that true?
|
1

I used try .. catch to distinguish branches from leafs. update No more exceptions :)

from collections import Iterable
tree = [[1,2,3],[4,5, [1, 6]],[6],[7],[8],[],[],[],[]]

def max_depth(tree, level=0):
  if isinstance(tree, Iterable):
    return max([ max_depth(item, level+1) for item in tree])
  else: # leaf
    return level

print max_depth(tree)
Improve this answer

2 Comments

I specifically do not want this recursive version because of stack limitations. I want to use my own stack (Q). I had the recursive version as: def max_depth(tree): def _depth(node): return 0 if tree[node] == [] else 1 + max(_depth(v) for v in tree[node]) return _depth(0)
I would also suggest against an except clause with no exception set to catch as that would make it impossible to interrupt the execution of your function in almost any way
1

After taking into account all the good feedback I got from Alex and Adonis and refining the code, I currently have the current version:

def max_depth_dfs(tree): # correct

max_depth, curr_depth, Q = 0, 0, [0]
visited = set()

while Q != []:

    n = Q[0]

    if n in visited:
        Q = Q[1:]
        curr_depth -= 1
        visited.remove(n) # won't go back, save memory 
        print 'backtrack from', n        
        continue

    # proper place to print depth in sync with node id
    print 'visiting', n, 'children=', tree[n], 'curr_depth=', curr_depth, 'Q=', Q,
    print visited # only current path, instead of visited part of tree

    if tree[n]:
        visited.add(n) # if leaf, won't ever try to revisit
        Q = tree[n] + Q
        curr_depth += 1
        max_depth = max(max_depth, curr_depth) # no need to check if depth decreases
    else:
        Q = Q[1:] # leaf: won't revisit, will go to peer, if any, so don't change depth
        print 'no children for', n

return max_depth
Improve this answer

Comments

0

Here is the non-recurison version:

from collections import Iterable

def max_depth_no_recur(tree):
  max_depth, node =  0, iter(tree)
  stack = [node]
  while stack:
    try:
      n = node.next()
    except StopIteration:
      if len(stack) > max_depth:
        max_depth = len(stack)
      node = stack.pop()
      continue

    if isinstance(n, Iterable):
        stack.append(node)
        node = iter(n)
  return max_depth
Improve this answer

7 Comments

This is very nice, but a lot of machinery. I was hoping for something simpler :-) (i.e. without Iterable, and without isinstance?)
The previous version didn't worked. This one does. Iterable is just to identify if node can be dug dipper.
Yes, that's why I was leaving the node id on the stack till all its children had been explored: I do Q = Q[1:] only when there is nothing to explore at that node anymore.
This version is very memory efficient. It holds lazy iterators on the local stack only and does deep-first walk.
Yes, the iterators are very efficient.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.