0

For a given, tree-like data structure:

 - Alan
     - Barbara
         - Charlie
         - Cecil
     - Brian
         - Chris
         - Candice
         - Cohen
     - Boromir
         - Corcoran
 - Arthur
     - Bort
         - Clive
         - Chad
     - Berman
         - Chud
 - Angel
     - Barry
         - Crick

All of my experience/research is around b-trees and binary trees and searching, traversing and balancing, as opposed to pruning.

Is there a known way, given a list of the leaf nodes (e.g. ["Cecil", "Candice", "Charlie", "Chad"]) to prune the tree and return only:

 - Alan
     - Barbara
         - Charlie
         - Cecil
     - Brian
         - Candice
 - Arthur
     - Bort
         - Chad
Improve this question
4
  • Hopefully this is not a "give the code", "do my homework" question, I'm aiming to find whether there is a known algorithm to reduce a tree, much like DFS/BFS exists.
    – StuperUser
    Jun 13, 2022 at 12:03
  • 3
    Assuming mutability, this is easy with a recursive function of the signature prune(tree, list) -> bool, where the return value indicates whether the tree contained one item from the list and therefore shouldn't be pruned from its parent node. For immutable data structures, the signature might look like pruned(tree, list) -> Option<Tree>
    – amon
    Jun 13, 2022 at 12:55
  • 1
    Concerning the downvotes: I did not downvote (yet), but askers on this site are expected to do some research before they ask, show us what they found and why it did not meet their needs. Some of our community members here are very trigger-happy with the downvote button whenever a question does not follow this guideline.
    – Doc Brown
    Jun 13, 2022 at 13:22
  • ... moreover, I think amon's comment above shows that it is pretty straightforward to solve this, so this task is probably too trivial for having a special name or algorithm.
    – Doc Brown
    Jun 13, 2022 at 13:31

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.