CODEWITHSUNDEEP
pythonimplementationdepth-first-search
Nikolai
Nikolai

Reputation: 347

Determining depth in a depth-first search

I am doing a task where I am to locate an animal in a tree.

In this case I am using depth-first search and a recursive implementation, all good so far.

However, I have to print out the depth of this animal within this tree. I simply don't know where to start, and I haven't found a lot of useful material online.

This is the class framework.

class Node:
    children = None
    ratatosk = None 

    def __init__(self):
        self.children = []
        self.ratatosk = False

Here is my implementation.

def dfs(root):
    for children in root.children:
        if root.ratatosk:
            return True # should return depth
        dfs(children)

Any help appreciated, thanks.

Upvotes: 1

Views: 86

Answers (1)

matsjoyce
matsjoyce

Reputation: 5844

Here's a version that returns both the depth and the found object:

def search(root):
    if root.ratatosk:
        return root, 0
    for i in root.children:
        found, depth = search(i)
        if found is not None:
            return found, depth + 1
    return None, 0

class Node:
    def __init__(self):
        self.children = []
        self.ratatosk = False

# example

thing = Node()
obj = Node()
layer1 = Node()
layer2 = Node()

thing.ratatosk = True
obj.children.append(layer1)
layer1.children.append(layer2)
layer2.children.append(thing)

found, depth = search(obj)
print(found, found is thing, depth)  # <__main__.Node object at 0x7fc652c5efd0> True 3

Upvotes: 1

Related Questions