CODEWITHSUNDEEP
javaandroidalgorithmtree
rakesh kashyap
rakesh kashyap

Reputation: 1466

Traversing a hierarchical List/Tree having reference to parent node in Java

I am trying to create a Hierarchical menu using https://github.com/bmelnychuk/AndroidTreeView

I would be retrieving my data from a REST service and a sample menu would look like below

[
  {
    "name": "parent 1",
    "code": "p1",
    "parent_code": "null",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "parent 2",
    "code": "p2",
    "parent_code": "null",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "child 1",
    "code": "c1",
    "parent_code": "p1",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "child 2",
    "code": "c2",
    "parent_code": "p1",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "grand child 1",
    "code": "gc1",
    "parent_code": "c2",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "grand child 2",
    "code": "gc2",
    "parent_code": "c2",
    "is_active": 0,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "grand child 3",
    "code": "gc3",
    "parent_code": "c2",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  }
]

I am trying to traverse the List and create a Hierarchical menu. I am traversing using the following code

for (ProductCategory prodCat :
                productCategories)
{
    if (prodCat.getParentCode().equalsIgnoreCase("null"))
    {
        // I found a parent node
        for (ProductCategory prodCatChild :
                productCategories)
        {
            if (prodCatChild.getParentCode().equalsIgnoreCase(prodCat.getCategoryCode()))
            {
                //I found all child nodes of the current parent
            }
        }
    }
}

My ProductCategory is defined as below

public class ProductCategory
{
    private String categoryName;

    private String categoryCode;

    private String parentCode;

    private Boolean isActive;

    private String storeId;
}

This piece of code has two issues.

How can I traverse having only reference to parent in the most efficient way?

Upvotes: 1

Views: 1566

Answers (1)

stemm
stemm

Reputation: 6050

I would advice you to use the Hash Map data structure in order to construct the tree with O(N) runtime complexity.

For simplicity, let's assume that your entities have the following structure (for the sake of simplicity I'm also violating the encapsulation principle inside the provided snippets of code):

class Item {

    // id of the item itself
    final String id;

    // id of the parent item
    final String parentId;

    // this list will contain the children of the given item
    // at the beginning this list is empty, and we are going to populate it
    final List<Item> children = new ArrayList<>();

    public Item(String id, String parentId) {
        this.parentId = parentId;
        this.id = id;
    }
}

In order to construct the tree you should maintain the mapping from item id to the item itself (which can be done using the java.util.HashMap data structure). After construction of the mapping, you can attach every node to its parent:

List<Item> constructForest(Item... items) {
    Map<String, Item> itemIdToItem = indexItemsById(items);
    List<Item> roots = attachToParents(itemIdToItem, items);
    return roots;
}

/**
 * Index all items by item id.
 * Returns the mapping from the item id to item.
 */
Map<String, Item> indexItemsById(Item... items) {
    Map<String, Item> itemIdToItem = new HashMap<>();
    for (Item item : items) {
        itemIdToItem.put(item.id, item);
    }
    return itemIdToItem;
}

/**
 * Attaches the children nodes to the parent nodes
 * Returns the list of root nodes of the constructed forest
 */
List<Item> attachToParents(Map<String, Item> itemIdToItem, Item... items) {

    List<Item> roots = new ArrayList<>();

    for (Item item : items) {
        if (item.parentId == null) {
            roots.add(item);
        } else {
            Item parent = itemIdToItem.get(item.parentId);
            parent.children.add(item);
        }
    }

    return roots;
}

The runtime complexity of the provided code is O(N).

Now, having the list of roots of the constructed trees, you can traverse them using any of the tree traversal algorithms, e.g. Breadth-first search (https://en.wikipedia.org/wiki/Breadth-first_search), Depth-first search (https://en.wikipedia.org/wiki/Depth-first_search), which also have the runtime complexity O(N).

Upvotes: 2

Related Questions