# 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);


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.

• does the tree have to be balanced? May 21, 2021 at 18:16
• @nirshahar no, it doesn't need to be balanced May 21, 2021 at 19:03
• consider the not-balanced tree where the root has two childs: the left child holds a fully balanced tree, and the right child holds a totally unbalanced tree (a "line" of nodes). Both of which are at the same depth. Then your statement is incorrect May 21, 2021 at 19:44
• @nirshahar In the example given in the question, the number of blue nodes on the left are $6$ and the number of blue nodes on the right are $3$. So this is a counterexample. Isn't it? May 21, 2021 at 19:46
• Yes, also works as a counter-example May 21, 2021 at 19:56

Notice that in any path from the root to a leaf, say $$v_1,\dots, v_k$$ we must have that the number of green nodes is at most $$1$$ (by the first property). Also, notice that the number of blue nodes in the path, is the depth of the leaf $$v_k$$ minus either one or zero, depending on whether there was a green node in that path.
1. Write at every leaf its depth (can be done in $$O(n)$$)
2. Write at every leaf whether there was a green node in the path from the root to it (think about it, it also can be done in $$O(n)$$)