In [1]:

    

class Node:
    def __init__(self,label,left,right):
        self.label = label
        self.left = left
        self.right = right
   
    def __repr__(self):
        left = 'None' if self.left is None  else self.left.label
        right = 'None' if self.right is None else self.right.label
    
        return "Node: (label={0},left_node_label={1},right_node_label={2})".format(self.label,left,right)    
    
    
    def search_children(self,target_label):
        if self.label == target_label:
            return (True,self)
        else:
            if self.left is None and self.right is None:
                return (False,None)
            
            if self.left is not None:
                return self.left.search_children(target_label)   
               
            if self.right is not None:
                return self.right.search_children(target_label)


    

In [2]:

    

#        a
#       / \
#      /   \
#     b    c
#    / \  / \
#   d  e b'  f
#  /
# c'

# I've created two nodes with labels 'b' and 'c' so that we can
# test whether we are indeed searching depth-first
b_prime = Node('b',None,None)
c_prime = Node('c',None,None)
f = Node('f',None,None)
e = Node('e',None,None)
d = Node('d',c_prime,None)
c = Node('c',b_prime,f)
b = Node('b',d,e)
a = Node('a',b,c)


    

In [3]:

    

# simple depth-first search in a binary tree
# a tree has no cycles!
def depth_first_search(root_node, target_label):
    return root_node.search_children(target_label)


    

In [4]:

    

depth_first_search(a,'a')


    

    
Out[4]:





(True, Node: (label=a,left_node_label=b,right_node_label=c))

In [5]:

    

depth_first_search(a,'d')


    

    
Out[5]:





(True, Node: (label=d,left_node_label=c,right_node_label=None))

In [6]:

    

# the node with label 'b' on the left subtree will be found first,
# because this is a depth first search
depth_first_search(a,'b')


    

    
Out[6]:





(True, Node: (label=b,left_node_label=d,right_node_label=e))

In [7]:

    

# this label was not found
depth_first_search(a,'j')


    

    
Out[7]:





(False, None)

In [8]:

    

# the node with label 'c' on the left subtree will be found first,
# because this is a depth first search
depth_first_search(a,'c')


    

    
Out[8]:





(True, Node: (label=c,left_node_label=None,right_node_label=None))

In [ ]: