Insert a node in Tree with more than 2 children per node

Question

I have a database table with parent child relationship and any parent can have any number of children but there will only be 1 parent at the root level. Data looks like below:

    TagID   ParentTagID   TagName
-------------------------------
    1        null          a
    2        1             b
    3        1             c
    4        1             d
    5        2             e
    6        4             f
    7        2             g

I want to fetch the records in java in a tree format. Although I can achieve this at SQL level itself using the below SQL but I want to extract the data from database as it is and perform the processing at java level so that the connection between java and SQL could be of minimum duration to avoid any latency from database side.

with cte as
(
  select * from TagValue
  where ParentTagID is null

  union all

  select s.* from TagValue s
  join cte c on s.ParentTagID = c.TagID
)
select * from cte

Using Java with taking help from other useful links, I have created a tree as per below:

public class MyTreeNode<T> {
    private T data = null;
    private List<MyTreeNode<T>> children = new ArrayList<MyTreeNode<T>>();
    private MyTreeNode<T> parent = null;

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

    public void addChild(MyTreeNode<T> child) {
        child.setParent(this);
        this.children.add(child);
    }

    public void addChild(T data) {
        MyTreeNode<T> newChild = new MyTreeNode<T>(data);
        newChild.setParent(this);
        children.add(newChild);
    }

    public void addChildren(List<MyTreeNode<T>> children) {
        for (MyTreeNode<T> t : children) {
            t.setParent(this);
        }
        this.children.addAll(children);
    }

    public List<MyTreeNode<T>> getChildren() {
        return children;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    private void setParent(MyTreeNode<T> parent) {
        this.parent = parent;
    }

    public MyTreeNode<T> getParent() {
        return parent;
    }
}

While inserting objects in this tree, I can use the below code:

MyTreeNode<Integer> root = new MyTreeNode<Integer>(1);

MyTreeNode<Integer> child1 = new MyTreeNode<Integer>(2);
child1.addChild(3);
child1.addChild(4);

MyTreeNode<Integer> child2 = new MyTreeNode<Integer>(5);
child2.addChild(6);

root.addChild(child1);
root.addChild(child2);
root.addChild(7);

root.addChildren(Arrays.asList(new MyTreeNode<Integer>(8),
        new MyTreeNode<Integer>(9), new MyTreeNode<Integer>(10)));

But this is a static code whereas the number of tags could be dynamic. I need a recursive solution to find a node based on ParentTag value and then insert the new tag as its child. Is there a recursive solution to do this? If there is any other out of the box data structure in Java 1.8 to perform this operation, that would also be useful.

Answer 1

Given a ResultSet, you would like to build your tree structure naturally, as follows:

while (... has more rows ...) {
    addNode(rs.ParentTagID, rs.TagID);

You need some type of container to store your tree nodes in. You could use a List however the performance will suffer when building the tree; adding a child requires finding its parent, and a list offers no quick way to do this. A Map however provides O(1) lookup.

The helper method addNode will keep the tree in tact: Find the parent, and add the child accordingly.

In summary the dynamic approach you are looking for is to iterate the result set, and repeatedly call addNode() passing both the parentId and childId (which is stored in the database). The root node is a special case (where parentId = null or 0) and is handled by addNode().

There was a slight modification to MyTreeNode to return the object (when adding a child); it used to be of type void.

Here is some sample code showing this approach.

public class MutipleTreeNode {

static Map<Integer, MyTreeNode<Integer>> nodeMap = new HashMap<>();

public static void main(String[] args) {

    // Here you would process your result set
    // Rather than simulate a result set, I just build some nodes manually
    addNode(0, 1);  // Root
    addNode(1, 2);
    addNode(1, 3);
    addNode(1, 4);
    addNode(2, 5);
    addNode(2, 7);
    addNode(4, 6);

    printTree();

}

private static void printTree() {
    for (MyTreeNode<Integer> node : nodeMap.values()) {
        if (node.getParent() == null)
            System.out.print("Root node: ");
        System.out.println(node.getData()+"; children="+node.getChildren());
    }

}

private static void addNode(int parentId, int childId) {
    MyTreeNode<Integer> childNode, parentNode;
    if (nodeMap.isEmpty())
        childNode = new MyTreeNode<Integer>(childId);
    else {
        parentNode = nodeMap.get(parentId);
        childNode = parentNode.addChild(childId);
    }
    nodeMap.put(childId, childNode);
}

public static class MyTreeNode<T> {
    private T data = null;
    private List<MyTreeNode<T>> children = new ArrayList<MyTreeNode<T>>();
    private MyTreeNode<T> parent = null;

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

    public void addChild(MyTreeNode<T> child) {
        child.setParent(this);
        this.children.add(child);
    }

    public MyTreeNode<T> addChild(T data) {
        MyTreeNode<T> newChild = new MyTreeNode<T>(data);
        newChild.setParent(this);
        children.add(newChild);
        return newChild;
    }

    public void addChildren(List<MyTreeNode<T>> children) {
        for (MyTreeNode<T> t : children) {
            t.setParent(this);
        }
        this.children.addAll(children);
    }

    public List<MyTreeNode<T>> getChildren() {
        return children;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    private void setParent(MyTreeNode<T> parent) {
        this.parent = parent;
    }

    public MyTreeNode<T> getParent() {
        return parent;
    }

    @Override
    public String toString() {
        return "[data=" + data + "]";
    }
}
}

Creates the output:

Root node: 1; children=[[data=2], [data=3], [data=4]]
2; children=[[data=5], [data=7]]
3; children=[]
4; children=[[data=6]]
5; children=[]
6; children=[]
7; children=[]