Given a tree, return a node such that if we root the tree from it, it becomes a magical panda tree which is a binary tree with each layer of nodes alternating between: red, black and white; in a regular pattern
ie. After rooting, nodes of each depth should have the same color & the should be alternating like White-Blue-Red-White-Blue .. you get the idea.
N <= 1e5
I've tried to break it up into cases:
No node with degree 3 can be the root If a node has degree two with same colored adjacent nodes, no other node can be the answer, there must be only one such node and we can do a level order traversal to check if it satisfies the coloring properties.
If a node has degree 2 with different colored adjacent nodes it cannot be the root. Not sure what to do with degree 1. Can't see a pattern.
I got this asked today in my google interview :/
Can't we just BFS from every node? Is there a bad case that can cause quadratic time complexity?
First, you need to ensure that it is a binary tree.
Any tree such that there exists: - Exactly one node with degree 2 - All other nodes are of either degree 3 or 1
If it was the case, then you found the root.
Now your goal to determine if it's a Magical Panda Tree or not, you can do it using DFS/BFS.
Why is there exactly one node of degree 2? What if some nodes have only one descendant?
Sorry, I assumed that it is a full binary tree (either 2 children or 0).
Here is another observation that will solve the problem: For every vertex, all of its adjacent must be in opposite color, otherwise it's not a Magical Panda Tree
If this condition is satisfied, then you can put the root at any vertex that has degree 2.