# Building a tree structure from pairs of parent-child to retrieve all ancestors of a leaf

I am trying to build a tree similar to this one :

      1
/ \
2   3
/|\
4 5 6
/
7


With that tree, I must be able to get all ancestors for each leaf.

In this example, this would be :

7 -> [4, 2, 1]
6 -> [2, 1]
5 -> [2, 1]
3 -> [1]


To build that tree, I can only use an unknown number of pairs of parent-child, which are added at runtime, one at a time.

Each time a new pair arrives, I have to update the tree.

For example, the tree is empty at the beginning.

Then I am given the pair 2, 4 Resulting tree :

  2
/
4


Then I am given the pair 1, 3 Resulting tree :

  2   1
/     \
4       3


Then I am given the pair 2, 5 Resulting tree :

  2   1
/|    \
4 5     3


Then I am given the pair 1, 2 Resulting tree :

    1
/ \
2   3
/|
4 5


You get the idea.

Here is my Node class :

public class Node<T> {
private T data;
private Node<T> parent;
private Map<T, Node<T>> children;

public Node(T data, Node<T> node) {
this.data = data;
this.parent = node;
}

public Node(T data) {
this.data = data;
}

public boolean hasChildren() {
if (this.children != null) {
return this.children.size() > 0;
}
return false;
}

public void addNode(Map<Long, Node<T>> tree, Node<T> node) {
tree.put((Long) node.data, node);
Node<T> parent = tree.get(node.parent.data);
if (parent != null) {
if (parent.children != null {
parent.children.put(node.data, node);
} else {
parent.children = new HashMap<T, Node<T>>();
parent.children.put(node.data, node);
}
}
}

public Map<Long, Node<T>> getLeaves(Map<Long, Node<T>> tree) {
Map<Long, Node<T>> leaves = new HashMap<Long, Node<T>>();
for (Entry<Long, Node<T>> node : tree.entrySet()) {
if (!node.getValue().hasChildren()) {
leaves.put(node.getKey(), node.getValue());
}
}
return leaves;
}

public Set<Node<T>> getAncestors(Node<T> leaf) {
Set<Node<T>> ancestors = new HashSet<Node<T>>();

if (leaf.parent != null) {
getAncestors(leaf.parent, ancestors);
}
return ancestors;
}

private void getAncestors(Node<T> leaf, Set<Node<T>> listOfAncestors) {
if (leaf.parent != null) {
}
}

public Map<Long, Set<Long>> transformToMap(Map<Long, Node<T>> tree) {
Map<Long, Node<T>> leaves = getLeaves(tree);
Map<Long, Set<Long>> hierarchy = new HashMap<Long, Set<Long>>();

for (Entry<Long, Node<T>> leaf : leaves.entrySet()) {
Set<Node<T>> ancestors = new HashSet<Node<T>>();
Set<Long> ancestorsId = new HashSet<Long>();
for (Node<T> node : ancestors) {