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.