depth-first search

dfs.py

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