# Checking two properties of a tree

I have the following definition:

A green-blue tree is a binary tree that follows the following properties:

• Each green node has only blue descendants.
• Every path that goes from a node to a leaf has the same number of blue nodes.

This is an example of a green-blue tree:

For the first part, we can ensure that every node has only blue descendants in $$O(n)$$, being $$n$$ the number of nodes.

The algorithm could be as follows:

``````bool descendants_condition(node):
if node == nullptr:
return true
if node.info == green;
return descendants_condition(node->left) and
descendants_condition(node->right);
else:
return only_blue_nodes(node->left) and
only_blue_nodes(node->right);
``````

And now, for the second part, I’m trying to avoid checking every path from every node to the leafs. I have the following intuition:

• If a node is a leaf, the condition is satisfied
• If a node is not a leaf, we should have the same number of blue nodes in the right and in the left.

However, this is not enough for me, and I would like to see a proof of this condition.