How to create list with recursive function

Question

This is the sample data (array of MenuModel);

this.menuItems = [
     {Id:1, itemName:'test-item1'},
     {Id:2, itemName:'test-item2'},
     {Id:3, itemName:'test-item3'},
     {Id:4, itemName:'test-item4',parentId:1},
     {Id:5, itemName:'test-item5',parentId:2},
     {Id:6, itemName:'test-item6',parentId:1},
     {Id:7, itemName:'test-item7',parentId:6}
];

Defination of MenuModel:

export interface IMenuModel{
    Id:number
    itemName:string;
    parentId?:number;
    childItems?:IMenuModel[];
}

Code is as follows

var tempItems = this.menuItems;
var itemsConstructed: IMenuModel[] = [];
tempItems.map((item: IMenuModel, i: number) => {
    var newItem: IMenuModel = { Id: item.Id, itemName: item.itemName, parentId: item.parentId, childItems: [] };
    var isInList: boolean = false;
    itemsConstructed.map((item_: IMenuModel) => {
        if (item_.Id == newItem.parentId) {
            item_.childItems ? item_.childItems.push(newItem) : [newItem];
            isInList = true;
        }
    });

    if (!isInList) {
        itemsConstructed.push(newItem);
    }
});

It works for one step deep, but cant place "test-item7" because its parent(test-item6) is also child of "item1". so I need to do it recursively. How can I achieve this?

awmleer · Accepted Answer · 2017-02-19 00:51:10Z

Since itemsConstructed is not a list but a tree, you should use DFS.

function search(items:IMenuModel[],id:number):IMenuModel{
  for(let i=0; i<items.length; i++){
    if(items[i].Id==id){
      return items[i];
    }else{
      if(items[i].childItems && items[i].childItems.lenght>0){
        let temp = search(items[i].childItems, id);
        if(temp==null){
          continue;
        }else{
          return temp;
        }
      }
    }
  }
  return null;
}

var tempItems = this.menuItems;
var itemsConstructed: IMenuModel[]=[];
tempItems.map((item:IMenuModel, i:number)=>{
    var newItem:IMenuModel={ Id:item.Id, itemName:item.itemName, parentId:item.parentId, childItems:[] };
    var isInList:boolean = false;
    if(newItem.parentId==null){//doesn't have parentId
      itemsConstructed.push(newItem);
      return;
    }
    var parentItem=search(itemsConstructed,item.parentId);
    if(parentItem==null){//doesn't exist
      itemsConstructed.push(newItem);
    }else{//exist in list
      item_.childItems?item_.childItems.push(newItem):[newItem];
    }
});

More about DFS and Tree_traversal.

Collectives™ on Stack Overflow

How to create list with recursive function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related