My approach, did a DFS on the tree, and built it from the leaves, assigning coins starting from the leaves as we go up.

  1. Every leaf gets a coin.
  2. Parent coins were assigned greedily, such that every alternate node gets a coin (in case of a single chain).
  3. States were given to see priorities in order of deciding when to give a coin, and states were passed by the children to the parents, not vice-versa.
  4. State 1 denotes that this node gets a coin.
  5. State 2 denotes that this is the parent of a node which has a coin, so we can leave out this one and the parent of this node will surely have to have a coin i.e. parent of any node with state 2 gets State 1 automatically.
  6. If root has state 2, it will only get a coin if it has only 1 child.
  7. For considering special cases where root might be the parent of a branch containing only 1 node, the parent of every leaf gets State 3 (same rules except State 2, just that if root has State 3, it will get a coin irrespective of how many children it has.)

My solution link :

My solution gives WA on every single Test case. Can I please know the flaws in my logic, and any counter case which this code fails ? I’d really appreciate the help :slight_smile: