Implement the data structure for storing an n-array tree that represents hierarchical data

Subtree-Intersection:

Implement the data structure for storing an n-array tree that represents hierarchical data. Each level of the tree is constrained to the corresponding level of a hierarchy. For eg: If the tree represents location data, we may have level1=states level2=cities level3=streets level4=blocks

Implement a method to compute a subtree-based intersection as follows: Inputs: SetA: Set of nodes from the tree that may belong to different levels (eg: Set of state, streets and cities) SetB: Disjoint set of nodes from the tree (eg: Set of states, blocks and cities)

Write an algorithm to: 1. detect the level of elements in each input set 2. Find sub-tree intersection: print elements from the lower level set(child level) such that there is an element in the other input set that is its parent.

Eg: Input tree = {(ROOT, Maharashtra), (ROOT, Karnataka), (Maharashtra, Mumbai), (Maharashtra, Pune), (Karnataka, Bangalore), (Mumbai, Worli), (Mumbai, Dadar), (Pune, Kothrud), (Pune, Wakad), (Bangalore, Jayanagar), (Bangalore, JP Nagar) }

Inputs to intersection method: 1. The Tree 2. SetA = {Wakad, Jayanagar, Pune, Worli} 3. SetB = {Dadar, Bangalore}

Output = {Jayanagar}

PS: 1. Please provide a good Class Design for representing the tree. 2. Design a good API for building the tree and performing search and find operations. 3. Suggest a good strategy to check which level a node from an input set belongs to. 4. Specify test cases for the sub-tree intersection method.