Simple depth first search

dfs.py

from __future__ import absolute_import, division, print_function


class Node(object):
    def __init__(self, value, parent, left=None, right=None):
        self.right = right
        self.left = left
        self.parent = parent
        self.value = value


class Tree(object):
    def __init__(self, value):
        self.root = Node(value, None)

    def add_left(self, value, node):
        if node.left:
            raise Exception('Already a node there')
        n = Node(value, node)
        node.left = n
        return n

    def add_right(self, value, node):
        if node.right:
            raise Exception('Already a node there')
        n = Node(value, node)
        node.right = n
        return n


def dfs(tree, target):
    node = tree.root
    return _dfs(node, target)


def _dfs(node, target):
    if not node:
        return False
    print('look at:' + node.value)
    if node.value == target:
        return node.value
    return _dfs(node.left, target) or _dfs(node.right, target)



t = Tree('a')
b = t.add_left('b', t.root)
c = t.add_right('c', t.root)
d = t.add_left('d', c)
e = t.add_right('e', c)
bb = t.add_left('bb', b)
bbb = t.add_left('bbb', bb)

assert dfs(t, 'a') == 'a'
assert dfs(t, 'd') == 'd'
assert dfs(t, 'bb') == 'bb'
assert not dfs(t, 'not_there')