graph.py

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

    def __repr__(self):
        return "[value: {}]".format(self.value)

    @staticmethod
    def dfs(n, v):
        if n.value is None:
            return None
        if n.value == v:
            return n
        else:
            r = None
            if n.left is not None:
                r = Node.dfs(n.left, v)
            if n.right is not None and r is None:
                r = Node.dfs(n.right, v)
            return r

    @staticmethod
    def bfs(n, v):
        queue, visited = [n], set()
        while queue:
            p = queue.pop(0)
            if p not in visited:
                visited.add(p)
                if p.value == v:
                    return p
                else:
                    if p.left is not None:
                        queue.append(p.left)
                    if p.right is not None:
                        queue.append(p.right)
        # test by returning visited as a list to preserve visited order


ds = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))

if __name__ == "__main__":
    print(Node.dfs(ds, 7))  # [value: 7]
    print(Node.dfs(ds, 8))  # None
    print(Node.bfs(ds, 5))  # [value: 5]
    print(Node.bfs(ds, 8))  # None