This question was asked recently in Google coding interview:
Design a tree-like data structure with two functionalities:
- SetRoot(int nodeId): sets the root of the tree to the given Id node.
- IsAncestor(int nodeId1, int nodeId2): return true/false if nodeId1 is ancestor of nodeId2.
Optimize DS for IsAncestor calls. Note that on calls of SetRoot, the connections direction may change.
I was asked to think of better time complexity than O(N), where N is no of nodes. Any ideas?
Comments (10)