1

I'm looking for some guidance in approaching a tree/graph traversal problem with the following specifications:

  1. There is one root node.
  2. The root node can potentially have infinite child nodes.
  3. Each child node can have only one parent, but can also itself be parent to potentially infinite child nodes, and so forth.
  4. This will, in a real-world scenario, in most cases be a small structure. However, it should still work for large structures, with regards to traversal and deletion.
  5. I'm most concerned with deletion, as deletion of a node MUST delete any of node's children, grand-children, etc. as well as any reference to the deleted node in the parent.

How would I approach this problem with efficiency in mind. I'm looking to implement something in Javascript/JQuery. I hope this is enough information and any advice is very much appreciated.

Thank you.

* EDIT/UPDATE * I think the structure described above will most closely resemble a directed graph and due to potentially infinite child nodes at each level, will not be a binary tree. Also, I don't know if I'm articulating this properly, but the structure is not laid out according to its node relationships, in the actual HTML code. In other words the visual/code design of the structure does not match the various parent/child relationships that are present in the JSON representation for example. This was a choice made by someone else but regardless, it is my job to implement traversal,insertion, and deletion.

I've looked around some more on SO and found the following link:

How to delete all related nodes in a directed graph using networkx?

The first answer in the link above is the closest I've found so far to a solution. But I don't understand how the "Worklist Algorithm" mentioned in the first answer, goes deeper than the first level?

Again, any help is appreciated.

Community
  • 1
  • 1
user2360062
  • 663
  • 2
  • 7
  • 19
  • Deleting the root node of a sub tree should remove all ancestors. Navigating the tree should be done with recursion. Related: [recursive find in a json object graph](http://stackoverflow.com/a/11657379/1026459) – Travis J Oct 16 '13 at 19:29
  • Here is a gist which i created couple of months back https://gist.github.com/vinothbabu/5519325... you can have a look at it. – Thalaivar Oct 16 '13 at 19:30
  • Thanks for the additional information. I've also updated my question above in an attempt to clarify it. – user2360062 Oct 17 '13 at 16:02

0 Answers0