Flat org structure to tree view in java

Question

I have my org structure as given below -

      T1
|''''   ''''|
T2          T3
|
T4

Stored in database as -

+----+---------+-----------+-----------+
| ID | TEAM_ID | PARENT_ID | TEAM_NAME |
+----+---------+-----------+-----------+
|  1 |       1 |         1 | T1        |
|  2 |       2 |         2 | T2        |
|  3 |       2 |         1 | T2        |
|  4 |       3 |         1 | T3        |
|  5 |       3 |         3 | T3        |
|  6 |       4 |         4 | T4        |
|  7 |       4 |         2 | T4        |
|  8 |       4 |         1 | T4        |
+----+---------+-----------+-----------+

And I want to re-build the above tree from flat data given in table above.

My current approach is -

Map<Long, List<TeamHierarchy>> tree = new HashMap<>();
        for (TeamHierarchy n : flatTeamStructure) {
            if (n.getParentTeamId() == n.getTeamId()) {
                if (!tree.containsKey(n.getParentTeamId())) {
                    tree.put(n.getParentTeamId(), new ArrayList<TeamHierarchy>());
                }
            } else {
                if (!tree.containsKey(n.getParentTeamId())) {
                    tree.put(n.getParentTeamId(), new ArrayList<TeamHierarchy>());
                }
                tree.get(n.getParentTeamId()).add(n);
            }
        }

Which is not completely correct because I get T4 also in T1's child. I only want to have immediate child. Any suggestion without recursion would be helpful.

Answer 1

I'm not sure it's the most efficient way but it should work. I would try to map each team Id to it's proper parent. The difficulty here is your table contains redundant information so you have to be able to weed it out.

The idea is to start building your tree from the root recursively modifying the parent if you find a better one deeper into the tree. Here's a quick example standalone program that should get you going.

public class TestTree {
    private static List<Entry> entries = new ArrayList<Entry>();

    public static void main(String[] args) throws Exception {
        // simulate the DB entries
        entries.add(new Entry(1, 1, 1, "T1"));
        entries.add(new Entry(2, 2, 2, "T2"));
        entries.add(new Entry(3, 2, 1, "T2"));
        entries.add(new Entry(4, 3, 1, "T3"));
        entries.add(new Entry(5, 3, 3, "T3"));
        entries.add(new Entry(6, 4, 4, "T4"));
        entries.add(new Entry(7, 4, 2, "T4"));
        entries.add(new Entry(8, 4, 1, "T4"));

        // the root is the one entry with no parent other than self
        int root = 1;

        // map all relationships to the root
        Map<Integer, Integer> tree = new HashMap<Integer, Integer>();   // ID -> parent ID
        buildTree(tree, root);

        System.out.println(tree);

        // From this Map, it should be pretty obvious how to build the tree.
    }

    private static void buildTree(Map<Integer, Integer> tree, int parentId) {
        boolean dirty = false;
        for(Entry entry : entries) {
            if(entry.parentId == parentId && entry.teamId != parentId) {
                tree.put(entry.teamId, parentId);
                dirty = true;
            }
        }

        if(dirty) {
            // Continue building the tree from each node that was updated
            for(Integer nodeId : tree.keySet()) {
                if(tree.get(nodeId) == parentId) buildTree(tree, nodeId);
            }
        }
    }

    private static class Entry {
        int id;
        int teamId;
        int parentId;
        String teamName;

        Entry(int id, int teamId, int parentId, String teamName) {
            this.id = id;
            this.teamId = teamId;
            this.parentId = parentId;
            this.teamName = teamName;
        }
    }

Update

For the recursive method haters (and in case you're tree is so deep that it blows up the method call stack):

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class TestTree {
    private static List<Entry> entries = new ArrayList<Entry>();

    public static void main(String[] args) throws Exception {
        // simulate the DB entries
        entries.add(new Entry(1, 1, 1, "T1"));
        entries.add(new Entry(2, 2, 2, "T2"));
        entries.add(new Entry(3, 2, 1, "T2"));
        entries.add(new Entry(4, 3, 1, "T3"));
        entries.add(new Entry(5, 3, 3, "T3"));
        entries.add(new Entry(6, 4, 4, "T4"));
        entries.add(new Entry(7, 4, 2, "T4"));
        entries.add(new Entry(8, 4, 1, "T4"));

        // the root is the one entry with no parent other than self
        int root = 1;

        // map all relationships to the root
        Map<Integer, Integer> tree = new HashMap<Integer, Integer>();   //    ID -> parent ID
        Stack<Integer> stack = new Stack<Integer>();

        stack.push(root);
        do {
            int parentId = stack.pop();

            if(buildTree(tree, parentId)) {
                // Continue building the tree from each node that was updated
                for(Integer nodeId : tree.keySet()) {
                    if(tree.get(nodeId) == parentId) stack.push(nodeId);
                }
            }
        } while(!stack.isEmpty());

        System.out.println(tree);

        // From this Map, it should be pretty obvious how to build the tree.
    }

    private static boolean buildTree(Map<Integer, Integer> tree, int parentId) {
        boolean dirty = false;
        for(Entry entry : entries) {
            if(entry.parentId == parentId && entry.teamId != parentId) {
                tree.put(entry.teamId, parentId);
                dirty = true;
            }
        }

        return dirty;
    }

    private static class Entry {
        int id;
        int teamId;
        int parentId;
        String teamName;

        Entry(int id, int teamId, int parentId, String teamName) {
            this.id = id;
            this.teamId = teamId;
            this.parentId = parentId;
            this.teamName = teamName;
        }
    }
}