0
$\begingroup$

I've a flat structure where a node references its parent instead of children

class Node(int Id, Node Parent, string Data);

Given a list of all nodes, and a search condition, I want to return the matches plus all ancestors and descendants

This what I'm trying to implement https://hshn.github.io/angular-ui-tree-search/

What would be a reasonably efficient algorithm to achieve this? I was aiming to build a tree as described here https://stackoverflow.com/questions/444296/how-to-efficiently-build-a-tree-from-a-flat-structure, and replicate the algorithm from the angular library above but it went over my head with all that OOP'ness

$\endgroup$
0
$\begingroup$

Given a tree, expressed with parent pointers, you can easily add child pointers: just traverse all nodes, and when you encounter a node $n$, look up its parent $p$, then add a child pointer from $p$ to $n$.

Given a tree and a search condition, you can find all matches by iterating over all nodes to see which ones satisfy the search condition. If you've augmented the tree to contain both parent pointers and child pointers, for each matching node, you can return its parent and its children using those pointers.

$\endgroup$
  • $\begingroup$ but when there are multiple matches, how do I prevent needless recomputations? if my second match is a descendant of my first match I don't have to do anything, if it is an ancestor of my first match I can skip that node when adding the descendants etc $\endgroup$ – Ernestine Holland Apr 18 at 6:24
  • $\begingroup$ @ErnestineHolland, why would there be any recomputation? Add the child pointers to all nodes once beforehand, and then you will never need to do it ever again. You don't re-do it every time you want to find matches. $\endgroup$ – D.W. Apr 18 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.