# Propagating node labels upwards in a tree

I am trying to think of an efficient way to synchronize a tree's nodes with the following rules.

Consider for instance this tree:

so the top of the heap is always B which can have many leaf-type nodes called G, or children which are node themselves called S, which can have leaves as well (G)

it is possible in the future that each G will have many leaves, but I assume the algorithm will be the same

So each G has a list of categories, that I want to syncronize (add and remove) with their parents.

so if g1 has categories [a,b,c] then B will have [a,b,c], but if g2 has categories [a,g,w] B will have [a,b,c,g,w] (all the categories of its children)

if the S nodes' leaves have categories it goes the same, each G of an S node will have categories that will propagate to their parent (which will get all the categories of its children) and in return will propagate the categories up to B, and B will have a union of all categories below it.

if any of the G leaves changes categories, or if the a G is added or an S is added the entire tree/heap need to syncronize according the new categories added.

I need the categories to be syncronized when added or removed. So every time a category is added I need the parent to get the categories of its children, which sort of scan the whole tree again

Is there an efficient way to do this?

• 1) This does not seem to relate to heaps at all. 2) So it's just the union of sub-tree labels you are after? What are the runtime contraints for adding, removing and searching nodes as well as retrieving labels? – Raphael Aug 28 '14 at 12:41
• yes, I may confuse heap, tree and other structures. sorry about that. I don't need searching for a category directly since I do that with SQL, so I don't to traverse it. For removing or adding, I don't need something spectacular, just not something that would take too long (lets say O(n) is fine, but I would prefer to limit the action to the subtree as much as possible) – Nick Ginanto Aug 28 '14 at 13:11
• I see. I recommend you first formulate your problem in an abstract fashion (as of now all we have is one example). Given an arbitrary tree $T$, how do you model node labels, which properties to they have to fulfill and what are the effects of tree manipulation operations? Once you write down answers to these questions in some structured way, (a) basic algorithm(s) probably stare(s) right at you. – Raphael Aug 28 '14 at 14:09
• What you are doing is design a data structure. To get the most suitable data structure for your application, you need to identify the following: [1] operations (such as look up categories given a node, add category, delete category) [2] the relative frequency each operations are used. Many data structure have the same functionality, but some can do 'look-up' quickly at the cost of slower 'update' for example. Knowing which operation you uses the most helps decide the most suitable implementation. – Apiwat Chantawibul Aug 28 '14 at 16:42

I understand your problem as follows (the best I could make of your presentation of it).

You have a tree rooted in node B. Each leaf is labeled wih categories. Each other node is labeled with the categories of all leaves below that node. The problem is to maintain proper labeling of all nodes, when changing the labels of leaves or adding or removing nodes from the tree.

The problem is easy when categories are added. You only have to propagate new categories from where they are added up to the root. The addition can come from adding a category to a leaf, or adding a new node with its own categories as a leaf, or with the categories of its daughters if it is an intermediate node.

The difficulty comes from removing categories, either by removing them from a leaf, or by removing a node and all the nodes below it. The difficulty comes from the fact that the categories it propagated upward may still have to be kept somewhere on the path, because they are provided by some other nodes.

However, this can be addressed very simply. Just keep a count of how many times a category is provided to a node from the leafs below that node. Then both addition and removal require only a bit of accounting. You remove a category from the labeling of a node when its count falls to zero for that node.

Time complexity

The complexity analysis below is added by an edit from Billiska. It can only be partial since the OP did not clearly state how the structure is to be used. In particular, it seems that he also intends to add or remove whole subtrees. But the information needed for the purpose is available from the root of the subtrees (assuming categories have been propagated beforehand in subtrees to be added), so that operating on whole subtrees is very similar to operating on leaves.

Let the tree have depth of $d$.

Look-up category of a given node is $O(1)$ since the category information is always stored up-to-date for each node.

Add a category to a given leaf node is $O(d)$ since the count of that category has to be incremented for every ancestor node up to the root.

Remove a category from a given leaf node is $O(d)$. Just the revert of add, we decrements the count of that category for every ancestor node up to the root.