Depth Of A Tree Using Dfs

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

Solution 1:

I found the bug!

ifnot 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.

defmax_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]]
        ifnot more:
            Q = Q[1:]
        else:
            curr_depth += 1
            Q = more + Q

    return max_depth

Solution 2:

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],[],[],[],[]]

defmax_depth(tree, level=0):
  ifisinstance(tree, Iterable):
    returnmax([ max_depth(item, level+1) for item in tree])
  else: # leafreturn level

print max_depth(tree)

Solution 3:

Here is the non-recurison version:

from collections import Iterable

defmax_depth_no_recur(tree):
  max_depth, node =  0, iter(tree)
  stack = [node]
  while stack:
    try:
      n = node.next()
    except StopIteration:
      iflen(stack) > max_depth:
        max_depth = len(stack)
      node = stack.pop()
      continueifisinstance(n, Iterable):
        stack.append(node)
        node = iter(n)
  return max_depth

Solution 4:

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

defmax_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 idprint'visiting', n, 'children=', tree[n], 'curr_depth=', curr_depth, 'Q=', Q,
    print visited # only current path, instead of visited part of treeif 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 decreaseselse:
        Q = Q[1:] # leaf: won't revisit, will go to peer, if any, so don't change depthprint'no children for', n

return max_depth