Hey folks
My friend shared a question asked to him in a MAANG interview:
You are given a Binary tree, each of the nodes of the tree is coloured with a colour belonging to {R, G, B}. You have to find all possible root nodes of the tree s.t. any path from the root to any node follows the colour pattern of R -> G -> B -> R -> G -> B -> R -> .... It need not start from R, it can start from any colour but needs to follow the RGB pattern cyclically.
My Solution:
My first observation is that: there can only be a single node that can be a root of such a tree. We can prove this by saying if there are two such nodes (let's say A and B), then the path from A to B follows the RGB pattern as well as the path from B to A, which is not possible; hence, there can only be a single root following the constraints.
My other observation is: If we choose some other node as root (than the one that follows the constraints), if we go down; path along one of the child will follow RGB pattern and the one along other child (this one has our answer root in its subtree) will follow BGR pattern (basically reverse of RGB). So the one that follows the BGR pattern will at some point reach our actual root node, and from that point onwards, the BGR pattern reverses to the RGB pattern. So basically, we look for this reversal point and this will only be our candidate answer.
Hence, we just verify if our candidate follows the constraints.
I'm not able to find this problem anywhere online. I found the problem quite interesting and hence am sharing here. But more importantly, I want to know if my solution is correct or not?
UPDATE:
kr25161 suggested an alternative solution, which I like even more:
"simultaneously you can say, if any node u is S[i] and all of its neigbours are S[(i + 1) % 3] where S = "RGB", you can check for u if it satifies in O(n). if it doesnt you return false instantly after the check. because any node apart from u cannot be root for this tree."
nice problem. your solution sounds reasonable.
Do you see any other solution?
nice comment. your feedback sounds reasonable.
i think your solution are correct. But i think that all the edge's direction are fixed in the begining, so a topological order can easily solve this problem.
The solution should work on any tree, not just binary tree
simultaneously you can say, if any node u is S[i] and all of its neigbours are S[(i + 1) % 3] where S = "RGB", you can check for u if it satifies in O(n). if it doesnt you return false instantly after the check. because any node apart from u cannot be root for this tree.
I like your solution; though same time/space complexity, yours is much easier to implement compared to mine
Nice idea! You could also find a potential root by starting at the root and repeatedly going to one of the children who has the value
S[(i + 2) % 3].A coloring problem for a colorblind person. P/s I really like the problem.
Now I know why it was difficult for me lol
Your ideas are nice, but I like doing a Reroot-tree dp in $$$O(n)$$$ without ever engaging with the problem
thanks! never heard of it.. will look into it
How were you able to solve this if you are a colorBlindCoder
similar to how you became master being dumb /s
what do you mean by "there can be only one node that follows such a pattern" ?
consider the tree: R-G-B, we can root the tree at any of the nodes
no.. if you root at R pattern should be B — G — R — G — B if you root at G pattern should be R — B — G — B — R so on. (consider the directed paths from root to all other nodes)
oh i see. thanks
2nd solution is so beautiful and elegant