1

Consider the following binary tree: (taken from here)

Given that leaf nodes will either be true or false, how can I find the branch (or branches) where all of the leaf nodes are true?

So if only 8, 5, 6 or 7 are true, then the first branch wouldn't match (it would need 9 to be true to match), but the second branch would match as all of its leaves are true.

Even identifying this name for this type of search would help so I can Google it.

1

2 Answers 2

2

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.

1
  • Thank you, I don't know Python, but I can see what's happening there. I'll give that a go. Feb 5, 2013 at 14:47
0

You can make a post-order tree traversal and mark each non-leaf node x true if both children have all leafs of their sub-tree true and false otherwise (it's an AND operation of the children's label). This way you recursevly mark the whole tree with your desired property.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.