**C++ : **

```
int utopianTree(int n) {
int height = 1;
bool wasEven = false;
if(n != 0){
if(n % 2 == 0){
n+=1;
wasEven = true;
}
while(n > 0){
//spring cycle
if(n % 2 == 1){
height *= 2;
//summer cycle
}else{
height++;
}
n--;
}
}
if(wasEven){
height /= 2;
wasEven = false;
}
return height;
}
```

*Explanation:*

*When receiving the height of the tree, the most outer if loop checks if n is equal to 0, if it is, the default height, which is 1, is returned. Else, there is some checking of height to do.*

*There is a pattern to this tree. If the cycle is odd (spring cycle), the height is doubled, else, it’s summer cycle, and the height is incremented by 1. *

*First, check if the total number of cycles is odd or even. If the cycle is even, set wasEven to true, then add the number of cycles by 1. Why add 1 if the total number of cycles is even? This is due to using a single while loop.*

*Take an example where total number of cycles is 4. Cycle 0 would be height 1, cycle 1 would be height 2 (spring), cycle 2 would be height 3 (summer), cycle 3 would be height 6 (spring) and cycle 4 would be height 7 (summer). However, in the while loop, we are counting downwards (till n is lesser or equal to 0), cycle 4 is height 2 (summer!), cycle 3 is height 4 (spring!), cycle 2 is height 5 (summer!), and cycle 1 is height 10 (spring!). Since the cycle is in reverse order, the height of the tree would become wrong, so only by adding 1 and turning it into an odd cycle, the cycle would be accurate. If you use a for loop (counting from year 1 to year n), you would probably not need to add this extra 1.*

*The while loop finds the height of the tree, then finally, if wasEven is true, divide the final height by 2 to get the actual height.*