How do I get an Array of recursive parent Ids from a category tree?-CodePudding

I have the following date structure (Recursive Tree of Categories that can have 0..n subCategories)

let categoryTree = [
  {
    id: 1,
    subCategories: [
      {
        id: 2,
        subCategories: [
          {
            id: 3,
            subCategories: [],
          },
        ],
      },
      {
        id: 4,
        subCategories: [
          {
            id: 5,
            subCategories: [],
          },
        ],
      },
    ],
  },
  {
    id: 6,
    subCategories: [
      {
        id: 7,
        subCategories: [
          {
            id: 8,
            subCategories: [],
          },
        ],
      },
      {
        id: 9,
        subCategories: [
          {
            id: 10,
            subCategories: [],
          },
        ],
      },
    ],
  },
];

What is the easiest way for a function which returns me an array of all recursive parent ids?

Examples:

getParentIds(3) // Should return [1,2]
getParentIds(8) // Should return [6,7]
getParentIds(4) // Should return [1]
getParentIds(1) // Should return []

My attempt at this, however, this only works sometimes and not for all of the possible ids.

function recursiveFindParent(id, categories) {

    for(let i = 0; i < categories.length; i  ){
        const c = categories[i];

    const subCat = c.subCategories.find(s => s.id === id);
    
    if (subCat !== undefined) {
      return c;
    } else {
      return recursiveFindParent(id, c.subCategories);
    }
  }

}

function getParentIds(id) {
  let foundParents = [];

  let parentId = id;
  let parent = null;

  while (parent = recursiveFindParent(parentId, categories)) {
    foundParents.push(parent.id);
    parentId = parent.id;
  }

  return foundParents;
}

console.log(getParentIds(3, categoryTree));

CodePudding user response：

We can see this as a variant of a Q A from a few days ago. I leave the explanation out, as that one covers it just fine. The only tweaks I had to make is to note the child node is called subCategories and to pull the id out of the returned list of nodes.

function * walk (xs, path = []) {
  for (let x of xs) {
    const newPath = path .concat (x)
    yield newPath
    yield * walk (x .subCategories || [], newPath)
  }
}

const ancestry = (pred) =>  (obj) => {
  for (let nodes of walk (obj)) {
    if (pred (nodes .at (-1))) {
      return nodes
    }
  }
  return []
}

const findAncestryById = (tree, targetId) => 
  ancestry (({id}) => id == targetId) (tree) .map (x => x .id) .slice (0, -1)

const categoryTree = [{id: 1, subCategories: [{id: 2, subCategories: [{id: 3, subCategories: []}]}, {id: 4, subCategories: [{id: 5, subCategories: []}]}]}, {id: 6, subCategories: [{id: 7, subCategories: [{id: 8, subCategories: []}]}, {id: 9, subCategories: [{id: 10, subCategories: []}]}]}];

[3, 8, 4, 1, 42] .forEach (
  (n) => console .log (`findAncestryById (${n}) //=> [${findAncestryById (categoryTree, n)}]`)
)

Also, please look at Mulan's excellent answer to that same question, which works quite differently.

CodePudding user response：

This question comes up a lot and I recently answered it in this Q&A. Your specific inquiry differs enough that I'll make a new post here, however much of the work is taken directly from the original answer.

generic find

Recursion is a functional heritage and so by using functional style we yield the best results. By decomposing the problem, we isolate concerns and make it easier for us to write individual solutions to the smaller sub-problems.

We start with higher-order find(t, func) that searches t using function, func, and returns all paths to the matched nodes.

If t is an array, for all child of t recur on the sub-problem find(child, func)
(inductive) t is not an array. If t is an object, then if the user-supplied function returns true for f, yield the singleton output, [t], otherwise for each path of the sub-problem find(t.subCategories, func), prepend t to the path and yield.
(inductive) t is neither an array nor an object. Stop iteration.

// node : { id: int, subCategories: node array }

// find : (node ∪ node array, node -> boolean) -> (node array) generator
function* find(t, func) {
  switch (true) {
    case is(t, Array):               // 1
      for (const child of t)
        yield* find(child, func)
      break
    case is(t, Object):              // 2
      if (Boolean(func(t)))
        yield [t]
      else for (const path of find(t.subCategories, func))
        yield [t, ...path]
      break
    default:                         // 3
      return
  }
}

Which depends on is -

// is : (any, any) -> boolean
function is(t, T) { 
  return t?.constructor === T
}

specialized find

Writing findById is a matter of specializing find. We assume id are unique and so return the path to the first matched node, if any. Otherwise return the empty path, [].

// findById : (node ∪ node array, number) -> node array
function findById(t, id) {
  for (const path of find(t, node => node.id === id))
    return path
  return []
}

checkpoint 1

To demonstrate proper behavior, I wrote a demo function which selects only the node id field and creates a ->-separated path. This allows us to us to easily confirm the output -

function demo(t, id) {
  console.log(
    `== id: ${id} ==`,
    findById(data, id).map(p => p.id).join("->")
  )
}

demo(data, 3)
demo(data, 8)
demo(data, 4)
demo(data, 1)

== id: 3 == 1->2->3
== id: 8 == 6->7->8
== id: 4 == 1->4
== id: 1 == 1

only the node ancestry

Your question asks specifically for the node's ancestry, which we can compute using another specialization. As we saw above, findById gets us all the way to the matched node. To select only its ancestry, we can simply slice the matched path, returning all but the last path element.

// findAncestryById : (node ∪ node array, int) -> node array
function findAncestryById(t, id) {
  return findById(t, id).slice(0, -1) // ✅ all but the last
}

demo

This time we will write demo to perform a query using findAncestryById -

function demo(t, id) {
  console.log(
    `== id: ${id} ==`,
    JSON.stringify(findAncestryById(data, id).map(p => p.id))
  )
}

demo(data, 3)
demo(data, 8)
demo(data, 4)
demo(data, 1)

== id: 3 == [1,2]
== id: 8 == [6,7]
== id: 4 == [1]
== id: 1 == []

You can verify the output below -

function is(t, T) { 
  return t?.constructor === T
}

function* find(t, func) {
  switch (true) {
    case is(t, Array):
      for (const child of t)
        yield* find(child, func)
      break
    case is(t, Object):
      if (Boolean(func(t)))
        yield [t]
      else
        for (const path of find(t.subCategories, func))
          yield [t, ...path]
      break
    default:
      return
  }
}

function findById(t, id) {
  for (const path of find(t, node => node.id === id))
    return path
  return []
}

function findAncestryById(t, id) {
  return findById(t, id).slice(0, -1)
}

function demo(t, id) {
  console.log(
    `== id: ${id} ==`,
    JSON.stringify(findAncestryById(data, id).map(p => p.id))
  )
}

const data = [{id:1,subCategories:[{id:2,subCategories:[{id:3,subCategories:[]}]},{id:4,subCategories:[{id:5,subCategories:[]}]}]},{id:6,subCategories:[{id:7,subCategories:[{id:8,subCategories:[]}]},{id:9,subCategories:[{id:10,subCategories:[]}]}]}];

demo(data, 3)
demo(data, 8)
demo(data, 4)
demo(data, 1)

gotcha

Did you notice findAncestryById(data, 1) returns an empty ancestry []? How would the output vary if 1 could not be found in the tree? This differs from the findById function which returns a valid empty path [] when a node is not found.

The reason findAncestryById needs a distinction is because [] is the same as [].slice(0, -1). For this particular function, you may want to return null if the node is not present in the tree. This is left as an exercise for the reader.

CodePudding user response：

My preference is always to write readable and maintainable code (e.g. what if your data structure changes and you have subC and subCategories in your tree?). So if you are ok using a library, this might be a good answer.

.as-console-wrapper {max-height: 100% !important; top: 0}

<script type="module">
import objectScan from 'https://cdn.jsdelivr.net/npm/[email protected]/lib/index.min.js';

const categoryTree = [
  { id: 1, subCategories: [{ id: 2, subCategories: [{ id: 3, subCategories: [] }] }, { id: 4, subCategories: [{ id: 5, subCategories: [] }] }] },
  { id: 6, subCategories: [{ id: 7, subCategories: [{ id: 8, subCategories: [] }] }, { id: 9, subCategories: [{ id: 10, subCategories: [] }] }] }
];

const getParentIds = objectScan(
  ['[*].**{subCategories[*]}'],
  {
    abort: true,
    filterFn: ({ value, context }) => value?.id === context,
    rtn: 'parents',
    afterFn: (state) => {
      state.result = state.result.map((p) => p?.id).filter((p) => p).reverse();
    }
  }
);

console.log(getParentIds(categoryTree, 3));
// => [ 1, 2 ]
console.log(getParentIds(categoryTree, 8));
// => [ 6, 7 ]
console.log(getParentIds(categoryTree, 4));
// => [ 1 ]
console.log(getParentIds(categoryTree, 1));
// => []
</script>

Disclaimer: I'm the author of object-scan