Поиск по глубине в Python никогда не возвращается True

Question

При поиске «3» в дереве, в котором явно содержится 3, код переходит в правильный оператор «if», но не возвращает True. Почему это?

class Node: 
    def __init__(self): 
     self.value = None 
     self.leftChild = None 
     self.rightChild = None 

def dfs(root, sought): 

    print "root", root.value 
    print "sought", sought.value 

    if root.value == sought.value: 
     print "inside root = sought" 
     return True 

    elif root.leftChild is not None and root.rightChild is not None: 
     dfs(root.leftChild, sought) 
     dfs(root.rightChild, sought) 
     return False 

Дерево, которое я создал с искомым значением заключается в следующем:

n1 = Node() 
n2 = Node() 
n3 = Node() 
n4 = Node() 
n5 = Node() 
n1.leftChild = n2 
n1.rightChild = n5 
n2.leftChild = n3 
n2.rightChild = n4 

n1.value=1 
n2.value=2 
n3.value=3 
n4.value=4 
n5.value=5 

s = Node() 
s.value=3 

Но выход оглупления. У меня есть подозрение, что отсутствие return True имеет какое-то отношение к рекурсивной природе Python?

> dfs(n1,s) 
> root 1 
> sought 3 
> root 2 
> sought 3 
> root 3 
> sought 3 
> inside root = sought 
> root 4 
> sought 3 
> root 5 
> sought 3 
> False 

Answer 1

Вы должны возвращать результаты из ваших рекурсивных вызовов:

res_a = dfs(root.leftChild, sought) 
    res_b = dfs(root.rightChild, sought) 
    return res_a or res_b