# How is the tree colored?

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.

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

• 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? Jul 24 at 23:10
• @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. Jul 25 at 8:26
• @WeatherVane I suppose by "half" here it doesn't mean precisely 0.5 Jul 25 at 8:35

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.