Fix a large integer $M$ and construct a binary tree as follows.
- Assign the root node by the integer $0$.
- If a node is assigned the integer $n$ and $n \leq M - 2$, then $n$ has two children and one of the children is assigned the integer $n + 1$ and the other is assigned $n + 2$.
- If a node is assigned the integer $n$ and $n = M - 1$ or $n = M$, then this node does not have any children.
- Repeat until the second rule cannot be applied (as in until none of the nodes can have any children since they are all assigned $M$ or $M - 1$).
So for an example if $M = 4$, the tree would look like
- First row: 0
- Second row: 1 2
- Third row: 2 3 3 4 (2 3 are children of 1 in 2nd row, 3 4 are children of 2 in 2nd row)
- Fourth row: 3 4 (children of 2 in 3rd row, none of the other elements in the third row have children)
My question is: When the construction ends, how many nodes will be assigned the integer $M$ and how many nodes will be assigned the integer $M - 1$?