0
$\begingroup$

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: enter image description here

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.

$\endgroup$
8
  • $\begingroup$ does the tree have to be balanced? $\endgroup$
    – nir shahar
    May 21, 2021 at 18:16
  • $\begingroup$ @nirshahar no, it doesn't need to be balanced $\endgroup$
    – Norhther
    May 21, 2021 at 19:03
  • $\begingroup$ 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 $\endgroup$
    – nir shahar
    May 21, 2021 at 19:44
  • $\begingroup$ @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? $\endgroup$ May 21, 2021 at 19:46
  • $\begingroup$ Yes, also works as a counter-example $\endgroup$
    – nir shahar
    May 21, 2021 at 19:56

1 Answer 1

1
$\begingroup$

This is not a proof for the statement (since the statement is incorrect if the tree is not balanced), but rather another way to think and solve the problem.

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.

So, in order to count the number of blue nodes in a path you have to do the following two things:

  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)$)

Then finally you go through all leaves, calculate the number of blue nodes using this information, and make sure all leaves have the same value of it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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