Tree search returning parents and children

Question

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

Answer 1

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.