Tree Coloring

You are given a binary tree root where the value of each node represents its color. In the tree there are at most 2 colors. Return whether it’s possible to swap the colors of the nodes any number of times so that no two adjacent nodes have the same color.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Tree-Coloring

Examples

Example 1

Input

• root =

Output

• answer = True

Explanation

We can color the root with 0, the next level 1s, third level 0s and fourth level 1s

Example 2

Input

• root =

Output

• answer = False

Explanation

There’s no way to color the nodes so that no two adjacent nodes have the same color.

Solution