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.