CODEWITHSUNDEEP
pythonalgorithmtreegraph-theorybreadth-first-search
ashukid
ashukid

Reputation: 353

How to find max depth of n-ary tree using bfs?

This is my node definition :

class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children

Now I've to find max depth in the tree. I'm using breadth-first search to mark the level of each node, then returning the max of levels.

This is my code :

def maxDepth(self, root):
    """
    :type root: Node
    :rtype: int
    """
    if(root == None):
        return 0

    q = []
    q.append(root)

    level={root.val:1}

    while(len(q)>0):

        s = q.pop(0)

        for c in s.children:
            q.append(c)
            level[c.val]=level[s.val]+1

    return max(level.values())

It's working on some cases but giving the wrong answer in many cases. I don't understand where I'm missing the concept?

Upvotes: 0

Views: 859

Answers (2)

nice_dev
nice_dev

Reputation: 17805

Since you know where you went wrong, you could do something like below to achieve max depth of the tree-

Pseudocode:

q = []
q.offer(root)
level = 1

while q.isEmpty() == false:

    size = q.size()
    for i = 0 to size:
        curr_node = q.poll()
        for each_child in curr_node:
            q.offer(each_child)

    level = level + 1

return level

Upvotes: 0

ashukid
ashukid

Reputation: 353

As suggested by @pfctgeorge, i was appending level according to node value, but there can be multiple nodes with same value as it's a tree, it'll give wrong answer in that cases.

Upvotes: 1

Related Questions