CODEWITHSUNDEEP
algorithmtree
Vivek Vardhan
Vivek Vardhan

Reputation: 1178

Finding Relationship between elements in a Tree structure, where no initial relationship

The question goes like "You are given a set of employees id and manager id, the manager is also an employee. Given any 2 employee id, task is to find relationship between them"

I thought the way, of creating Tree, and then find Lowest Common Ancestors and then, find the relation.

But, problem i am getting in creating the tree. Initially, i can have inputs, which are not related, i.e. the first two elements need not to have direct relationship between them (I am given with employee id and their manager id. Suppose first two entries are-- "emp-id-:1 and mangr-id-2" and "emp-id: 3, manager id:4", then i will have two roots, one with 4, and child 3, other root=2, and child 1, no relationship.

With complete data set, there will be relationship. How to tackle this problem

Note: In one file, i am provided with the complete dataset, if you will make tree, eventually they will become connected.

Also, a manager can have more than 2 juniors, so Binary Tree will not work.

Upvotes: 0

Views: 762

Answers (1)

amit
amit

Reputation: 178461

You can build a forest initially, and when you have a connection, join trees in the forest.

If the hirerchy is indeed tree-like, by doing so you will end up with a tree - as expected.

Regarding "no binary tree" - no problem, use a generalized tree. The implementation (in java-like language) would be something like:

class Node<Key> {
    Node<Key> father;
    final Key root;
    final List<Node<Key>> sons = new LinkedList<Node<Key>>();
    //constructor, methods and more fields if needed
}

One more thing - I'll add an extra dictionary (hash based/ tree based) to map from the employee/manager key to the node object representing this employee.
If using the above data structure, the map will be something like Map<Key, Node<Key>>.

Upvotes: 1

Related Questions