0
$\begingroup$

(I was not really sure in which "stackexchange" I should put this question. I hope CS is ok.)

Let's say I have the following tree A. Every node has a unique ID, which will be counted up, beginning from 0. The ID counting is taking place in breadth-first order. Original Tree

Now I want to pick out a part of the graph A. The information of the subtree is given by a node ID in the original tree A.

Example

Let's say the new tree starts with the node ID 3 of the original tree. For this example, the tree depth has an offset of 1 (because 3 is in depth 1 of the original node). The result is the following enter image description here

You might have noticed that the new tree have the same structure than the old tree. The unique ID of each node in the new tree, will also be counted up in breadth-first order. In the brackets, you can see the link to the original node tree A.

Background

The reason, why I need this node link is the fact that I need to copy some node properties from the original tree node to the new tree node.

Question

What is the mathematical relation between the unique node IDs of the new tree and the node IDs of the original tree? I want to compute the ID's of the old tree, based on the ID's of the new tree.

Thanks for any help.

$\endgroup$
  • 1
    $\begingroup$ We have one answer that thinks you want to compute the ID of the new tree given the old one (which is possible but takes as long as just computing IDs from scratch), and one that thinks you want to compute the ID of the old tree given the new one (which is impossible). Could you clarify which direction you're trying to go in? $\endgroup$ – David Richerby Aug 30 '16 at 7:34
  • $\begingroup$ I want to compute the ID's of the old tree, based on the ID's of the new tree. I added this information to the question. $\endgroup$ – eljobso Aug 30 '16 at 7:35
1
$\begingroup$

I don't think there is any "mathematical relationship". Observe that if you change the tree around the extracted subtree, the original IDs change arbitrarily.

You should copy properties while creating the copy of the tree you want to extract. Perform a tree traversal on the subtree in question and do everything in one pass.

You can also link new nodes to the old ones in case you need the relationship later.

$\endgroup$
0
$\begingroup$

This answer was based on a msiunderstanding of the question but I'll leave it here in case it turns out to be useful to anyone.


Clearly, the root of your subtree goes to ID 0 from whatever ID it originally had.

Now, consider the leftmost child on some row of the subtree. Let that vertex's ID in the original tree be $i$. If $i$'s parent is the root of the subtree, let $j$ be its ID in the original tree; otherwise, let $j$ be the ID of the parent's rightmost sibling (again, in the original tree). Finally, let $k$ be the ID of vertex $j$ in the new tree.

Notice that, in going from the new tree to the old one, you've deleted every vertex whose ID $x$ satisfies $j < x < i$. So, we need to subtract $i-j-1$ from $i$'s ID. But, also, we deleted $j-k$ vertices before vertex $j$, so we need to subtract that off, too. So, vertex $i$ becomes vertex $i-(i-j-1)-(j-k)=k+1$.

And, at this point, we realise we're wasting our time. Trying to update the vertex IDs intelligently has caused us to do a breadth-first search of the new tree, setting the ID of each vertex to be one more than the ID of the previous vertex in the subtree. In other words, you can forget about trying to do anything smart and just renumber the vertices of the subtree in the obvious way.

$\endgroup$
  • $\begingroup$ I understood the question so that the reverse function was the interesting thing so they can find the original nodes in the original tree later, by ID in the new tree. $\endgroup$ – Raphael Aug 29 '16 at 14:08
  • $\begingroup$ @Raphael Hmm. I didn't get that impression but maybe the question needs to be clarified. $\endgroup$ – David Richerby Aug 30 '16 at 7:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.