Skip to content

Instantly share code, notes, and snippets.

@alexminnaar alexminnaar/dfs.py
Created Jun 17, 2019

Embed
What would you like to do?
depth-first search
class Node:
def __init__(self, x):
self.val = x
self.children = []
def dfs(node, target):
# if the node is found then return it
if node.val == target:
return node
if node.children:
for child in node.children:
# if the child is the target the child node will be returned, if not then False will be returned
res = dfs(child, target)
# if False then don't return anything and continue searching
if res:
return res
return False
#create tree
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")
g = Node("g")
h = Node("h")
a.children = [b, c]
b.children = [d, e, f]
c.children = [g]
g.children = [h]
#search from the root for the given target
node = dfs(a, "g")
if node:
print node.val
else:
print node
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.