CODEWITHSUNDEEP
javarecursiontree
Tiny
Tiny

Reputation: 743

How to get recursively get all leaves of a Tree Structure in Java

I have a Database Table of a Tree Nodes as below. I want to make a ArrayList in Java out of these Tree Nodes. the Arraylist will recursively fetch all the Tree Nodes in a Recursive Format in Java.

Input:

Database Table

Name            ID      Parent_ID
Parent          1   
Child-1         2           1
Child-1.1       3           2
Child-1.1.1     4           3
Child-2         5           1
Child-3         6           1
Child-1.1.1.1   7           4
Child-1.2       8           2

I want to make an ArrayList of the above table in the below Java format where Sub is list of the Child Nodes, if no Child Node then Sub is Null.

public class Node {

    private String id;
    private String name;
    private String type;
    private String value;
    private List<Node> sub;
}

Output:

  1. Parent
    • Child-1
      • Child-1.1
        • Child-1.1.1
          • Child-1.1.1.1
      • Child-1.2
    • Child-2
    • Child-3

Can someone please help in creating a recursive function in Java to implement the above.

Upvotes: 3

Views: 7133

Answers (3)

Guy Ben Hemo
Guy Ben Hemo

Reputation: 110

Recursive function: 

public void printTree(Node tree,int num)
{
    if(tree==null || tree.getSub()==null)return;
    for(Node n : tree.getSub())
    {
    System.out.println(new String(new char[num]).replace("\0", "   ")+"*"+n.getName());
printTree(n,num+1);
}
}

public void callRec(Node tree)
{
    System.out.println(tree.getName());
    printTree(tree,1);
}

The result will be: 

Parent
*Child-1
  *Child-1.1
     *Child-1.1.1
        *Child-1.1.1.1
  *Child-1.2
*Child-2
*Child-3

Upvotes: 1

Codor
Codor

Reputation: 17605

The problem can be solved in two steps as follows, where the notation is some Java-ish pseudocode. First, all of the database rows have to be put in a List<Node> Nodes, where Node should have an additional member ParentID and the actual tree structure has to be built. This can be done as follows in time O(n^2), which is not optimal, but makes no additional assumptions on the node indices.

for (int i = 0; i < Nodes.Count(); i++) // iterate nodes
{
    for (int j = 0; j < Nodec.Count(); j++) // search parent of i-th node
    {
        if (Nodes[j].id.Equals(Nodes[i].ParentID)) // j-th node is parent of i-th node
        {
            Nodes[j].sub.add(Nodes[i]); // add i-th node to children of j-th node
        }
    }
}

Afterwards, the leaves can be identified easily as these are the nodes which have no children.

for (int i = 0; i < Nodes.Count(); i++)
{
    if (Nodes[i].sub.Count() == 0) // i-th node is a leaf
    {
        // do something with a leaf
    }
}

Note that I am not too familiar with Java from the top of my head, but the algorithmic idea should be understandable.

Upvotes: 0

noel zubin
noel zubin

Reputation: 672

Here is a rough algo:

ArrayList<Integer> ar = new ArrayList<Integer>();

public extract(node root){
    foreach(node i : root.sub)
        extract(i);
    ar.add(i.value);
}

Upvotes: 0

Related Questions