You can use a recursive function, diving deeper into the tree and determining bottom-up whether for a certain branch all leaves are true. Those branches can then be stored in some list.
Here's some Python code. Call this function with the tree's root node as the first parameter and an empty list as the second, and the list will be populated with the correct branches.
def allTrue(node, trueList=[]):
if isLeaf(node):
return node.value == True
else:
leftTrue = allTrue(node.left, trueList)
rightTrue = allTrue(node.right, trueList)
bothTrue = leftTrue and rightTrue
if bothTrue:
trueList.append(node)
return bothTrue
One thing to look out for: Many programming languages try to be clever, or lazy, by not evaluating the second argument of x and y
, if x
is false already. In this case, however, this would result in not visiting the right branch if the left branch is not all-true, missing out some all-true branches. Thus the recursive calls better go to separate lines.