2
$\begingroup$

Not relevant fiction context

Paul's journey in the mathematical forest began this early morning. You know, he is a Biomathologist! He saw a lot of spectacular plants, geometrical flowers and fractal cabbages.

Now, he is taking a moment for himself. He sit on a perfect cube and deeply breath contemplating the math world that is surrounding him.

Paul's gaze is soon attracted to a binary tree.

The binary tree has two colors, red and grey and grows with a logical pattern.

Mysterious half binary tree

After looking at it for a bit, Paul realizes that the tree is not colored symmetrically so he correctly guesses that what he is looking at is only half of the tree.

He wants to understand the color pattern to predict how the future leaves will be colored.

When the b-tree grows, it adds 1 layer in the top, spawning two leaves for each current top node per year. So, if at year 0 we have only the root, this tree is at year 6. Also the color of nodes does not change anymore once they are spawned.

Can you help him?

Hints

After a while Paul decides to approach the tree and see it fully: Full tree The root node color is irrelevant also the fact that it is not centered perfectly.

Paul observes that as soon as a grey node is encountered while traversing the tree, all the nodes above it are grey too. So the properties of a grey node are inherited by all the spawned node from that node.

Tree at year 8 (only the original observed half) Half tree at year 8

last hint

Improve this question
$\endgroup$
3
  • $\begingroup$ Re is only half of the tree. When the tree shown grows it does not double the number of nodes.The next generation has $n \times 2 + 1$ nodes. So will there be a missing node? $\endgroup$
    – Weather Vane
    Jul 24 at 23:10
  • $\begingroup$ @WeatherVane I've added the full tree in the hints and a brief description on how a b-tree grows each year. No node will be missing. Proposing only half of the tree was done merely to avoid the solvers to handle a very large image. $\endgroup$
    – 10010100102ohno
    Jul 25 at 8:26
  • $\begingroup$ @WeatherVane I suppose by "half" here it doesn't mean precisely 0.5 $\endgroup$
    – justhalf
    Jul 25 at 8:35

1 Answer 1

Reset to default
4
$\begingroup$

Let's call the path of a leaf the sequence of 0 and 1 that describe it's path from the root, as follow :

  • The root as an empty path []
  • The path of a node is the path of it's parent with an additionnal member: 1 if it's the left child, 0 if it's the right one.

When a new layer is added, the leaf is colored with the following rules :

  • Grey if the first half of the path is the exact same as the second half. (Only leaves with path of even length can satisfy this condition)
  • Grey if it's parent is grey
  • Red otherwise

Improve this answer
$\endgroup$
0

Your Answer

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

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