Best way to represent a tree of unknown depth of the same type of object in JavaScript/TypeScript?

user_259648 0
Viewed 94

The obvious answer here is to have a single class representing the object, then a reference to the parent object if there is one. The query across the tree would be to start at a given node of the tree and return all parent objects of that node. Each node will have only one direct parent node.

Is there a better way to do this computationally or from a software design perspective?

EDIT: Looking for computational complexity improvement suggestions or maintainability suggestions. Memory is not a huge issue here.

typescript tree javascript
1 Answers

@Thomas a relational one. Not sure what our team's opinion is on stored procs but if there is compelling enough reason to use them I'm sure I can make the case.

In a relational DB I would use a common-table-expression

WITH foo AS   
(  
    -- your start node
    SELECT * 
    FROM MyData AS d
    WHERE d.id = 123

    UNION ALL  

    -- traversing up
    SELECT parent.*
    FROM MyData AS parent
    JOIN foo AS child
      ON parent.id = child.parentId
)
-- selecting the data you want to return from the CTE
SELECT * FROM foo;

In JS terms, here a description what the above query does:

// initial SELECT
var foo = myData.filter(item => item.id === 123);

// UNION ALL + SELECT with JOIN onto `foo`
for (let i = 0; i < foo.length; ++i) {
  foo.push(...myData.filter(item => item.id === foo[i].parentId));
}

console.log(foo);

only that a DB select is way faster and more performant than the Array#filter() in the JS code, but basically they produce the same result; a list of (0 or more) matches

user_65672750
Related