Java: Construct a tree (with duplicate nodes) from a list of pairs

Question

I would like to construct a tree from a list of pairs.
The pairs are represented in the following way: child node/parent node.
Example:
2177 / 2178
2157 / 2178
2179 / 2177
2177 / 2157
2500 / 2177

Out of these pairs I would like to construct the following tree:

              2500        
                /
2179        2177
    \         /
   2177   2157
       \    /
        2178

I know that this is possible when all nodes have distinct values. But is there also a way if the nodes can have duplicate values like in this example?

It very much depends on the "kind" of tree you want to use; and the "properties" that your tree offers. In other words: we can' tell. You design your tree, and when you have specific questions, ask. As of know, your question is too broad/unclear. — GhostCat, Oct 25 '16 at 11:57
Your tree definition is not univocal, since you didn't explain how you can build the tree unambiguously. E.g. how did you decide which node you should choose when you add a child? e.g. 2/1; 3/2; 3/1; 4/3 <<-- which "3" should I use? — Sampisa, Oct 25 '16 at 12:19
Lets leave Java and programming languages aside. Basically, I would like to know if it is possible to construct a tree out of a list of child node/parent node pairs which express a relation. I know that this is possible when all treen node values are distinct, see http://stackoverflow.com/questions/30570146/convert-java-arraylist-of-parent-child-relation-into-tree for example. My case is a bit different, as the tree may contain duplicate node values (see node value 2177 in the example). — Christian Guetter, Oct 25 '16 at 12:21
It is possible, you just did it. It is not the only solution though. — Thorbjørn Ravn Andersen, Oct 25 '16 at 12:22
Sorry for being imprecise, English is not my native language. I wanted to know if the list of directed relations in my example contains enough information to construct exactly the one tree in my example. As far as I understand Thorbjørn's and Sampisa's comments, this is not possible, as there is more than one solution. — Christian Guetter, Oct 25 '16 at 12:31

Sampisa · Accepted Answer · 2016-10-25T13:14:17.437

If your purpose is just to build a tree, you can use something like this. It keeps a map of nodes (map "previous"), since there are no order infos to use. Note that tree built is NOT univocal:

package org.norsam;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author samuele m.
 *
 */
public class Mu
{

    // nodes with that value
    private Map<Integer, Set<TItem>> previous = new HashMap<>();

    private TItem root = null;

    public void addItem(Integer child, Integer parent)
    {
        // find a parent
        TItem tparent = findAParentLike(parent);
        // create child and add it to the parent
        TItem titem = new TItem(child);
        tparent.addChildren(titem);
        // add children to the map of "existent" elements
        if (!previous.containsKey(child)) {
            previous.put(child, new HashSet<TItem>());
        }
        previous.get(child).add(titem);
    }

    /**
     * Which node has this value?
     *
     * @param parent
     */
    private TItem findAParentLike(Integer parent)
    {
        if (root == null) {
            root = new TItem(parent);
            previous.put(parent, new HashSet<TItem>());
            previous.get(parent).add(root);
            return root;
        }
        if (!previous.containsKey(parent)) {
            throw new RuntimeException("Node " + parent + " not found");
        }
        Set<TItem> elems = previous.get(parent);
        return elems.iterator().next(); // one "random"
    }

    public void visit()
    {
        visit(root, ""+root.value);
    }

    private void visit(TItem elem, String base)
    {
        for (Integer child : elem.children.keySet()) {
            System.out.println(base + ":" + child.intValue());
            for (TItem item : elem.children.get(child)) {
                visit(item, base + ":" + child.intValue());
            }
        }
    }

    public static void main(String[] args)
    {
        Mu mu = new Mu();
        mu.addItem(2, 1);
        mu.addItem(3, 2);
        mu.addItem(4, 3);
        mu.addItem(4, 2);
        mu.addItem(5, 4);
        mu.addItem(6, 4);
        mu.addItem(5, 4);
        mu.addItem(6, 2);
        mu.addItem(7, 6);
        mu.addItem(9, 1);

        mu.visit();
    }
}

class TItem
{
    public int value;
    public Map<Integer, Set<TItem>> children = new HashMap<>(0);

    TItem()
    {
    }

    TItem(int value)
    {
        this.value = value;
    }

    void addChildren(TItem titem)
    {
        if (!children.containsKey(titem.value)) {
            children.put(titem.value, new HashSet<TItem>());
        }
        children.get(titem.value).add(titem);
    }
}

with the following output (on my laptop):

1:2
1:2:4
1:2:6
1:2:6:7
1:2:3
1:2:3:4
1:2:3:4:6
1:2:3:4:5
1:9

or this alternative one, equivalent to the previous one:

1:2
1:2:4
1:2:6
1:2:3
1:2:3:4
1:2:3:4:6
1:2:3:4:6:7
1:2:3:4:5
1:9

Java: Construct a tree (with duplicate nodes) from a list of pairs

1 Answers1