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
5
  • 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
    Commented 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
    Commented 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
    Commented 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
    Commented Jun 13, 2022 at 13:31
  • Here is an example: onlinegdb.com/p5ykM8AS9 Commented Apr 12, 2023 at 3:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.