Question 271602 in Javascript Question posted in
A very good W3school tutorial can be found here.

Get all descendants in a tree in javascript

Given a basic tree like this:

[
  {
    id: "1"
  },
  {
    id: "2"
  },
  {
    id: "3"
  },
  {
    id: "2.1",
    parent_id: "2"
  },
  {
    id: "3.1",
    parent_id: "3"
  },
  {
    id: "3.2",
    parent_id: "3"
  },
  {
    id: "3.1.1",
    parent_id: "3.1"
  },
  {
    id: "3.1.1.1",
    parent_id: "3.1.1"
  },
  {
    id: "3.1.1.1.1",
    parent_id: "3.1.1.1"
  },
  {
    id: "bohemian rhapsody",
    parent_id: "3.2"
  }
]

I want to be able to get all descendants starting at an arbitrary level (id).

This works but I am questioning if this is the most efficient way to do this because essentially I am scanning the array at each level

let source = []; // my array here
let getDescendants = (id, source) => {
    let result = [];
  
    for (let node of source) {
     if (node.id === id) {
        result.push(node);
     } else if (node.parent_id === id) {
        result.push(...getDescendants(node.id, source));
     }
    }
  
    return result;
};

Expected output of the above when run against ‘3’ is

[{ id: "3" }, { id: "3.1", parent_id: "3" }, { id: "3.1.1", parent_id: "3.1" }, { id: "3.1.1.1", parent_id: "3.1.1" }, { id: "3.1.1.1.1", parent_id: "3.1.1.1" }, { id: "3.2", parent_id: "3" }, { id: "bohemian rhapsody", parent_id: "3.2" }]

Note: I don’t particularly care if this is breadth first or depth first; just that it is the most performant approach.

Tags:

2

Answers


  1. 0

    You could perform a search with a single pass. As your dataset grows large, this would be a more performant solution, particularly in a heavily unbalanced tree as it would be comparing an O(N) solution to an O(N*N) solution.

    let getDescendants = (id, source) => {
    let result = [];
    let prefix=id + '.';
    for (let node of source) {
        if (node.id === id || node.parent_id === id 
          || node.parent_id && node.parent_id.startsWith(prefix)) {
            result.push(node);
        }
    }
    return result;
}

    Your optimal solution is affected by how you’re representing your tree as a list. If you were to transform your tree into an object that more closely represents the tree’s structure, your recursive approach could be scoped down to the children of your current node without traversing your entire list.

    [
  {
    id: "1"
  },
  {
    id: "2",
    children:[
      {
        id: "2.1",
      }
    ]
  },
  {
    id: "3",
    children:[
      {  
        id: "3.1",
        children:[
          {
            id: "3.1.1",
            children:[
              {
                id: "3.1.1.1",                  
                children:[
                  {
                    id: "3.1.1.1.1",
                  }
                ]
              }
            ]
          }
        ]
      },
      {
        id: "3.2",
        children:[
          {
            id: "bohemian rhapsody",
          }
        ]
      }
    ]
  }
]
    Login or Signup to reply.
  2. 0

    Here is an alternative solution that works without the .startsWith() restriction.

    const obj=[
  {
id: "1"
  },
  {
id: "2"
  },
  {
id: "3"
  },
  {
id: "two-one",
parent_id: "2"
  },
  {
id: "three-one",
parent_id: "3"
  },
  {
id: "3.2",
parent_id: "3"
  },
  {
id: "3.1.1",
parent_id: "three-one"
  },
  {
id: "3.1.1.1",
parent_id: "3.1.1"
  },
  {
id: "3.1.1.1.1",
parent_id: "3.1.1.1"
  },
  {
id: "bohemian rhapsody",
parent_id: "3.2"
  }
].reduce((a,c)=>(a[c.id]={...c,children:[]},a),{}); // create an object with id as keys
const arr=Object.values(obj);
arr.forEach(o=> // assign children to a parent
 o.parent_id && obj[o.parent_id].children.push(o));
const res=arr.filter(o=>!o.parent_id);

// show resulting object tree:
console.log(res);
    1. The array is turned into an object with ids as keys
    2. In a forEach() loop over all .values() of the object each element is pushed into its parent object’s children array
    3. Lastly, only those values in obj that do not have a parent_id are retained in a .filter() operation and stored in the solution array res.
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search