4
\$\begingroup\$

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) {
            listOfAncestors.add(leaf.parent);
        }
    }

    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>();
            ancestors.addAll(getAncestors(leaf.getValue()));
            for (Node<T> node : ancestors) {
                ancestorsId.add((Long) node.data);
            }
            hierarchy.put((Long) leaf.getKey(), ancestorsId);
        }
        return hierarchy;
    }
}

Can it be improved ?

\$\endgroup\$
  • \$\begingroup\$ Could you show some code for how your example pairs would be created into a tree? \$\endgroup\$ – Simon Forsberg Sep 9 '15 at 23:29
  • \$\begingroup\$ Are you on Java 8 as well? \$\endgroup\$ – h.j.k. Sep 9 '15 at 23:34
  • \$\begingroup\$ How does this work when you have multiple unrelated trees, like in the beginning of your example? \$\endgroup\$ – dfhwze Jun 4 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.