Get mathematical relation of node IDs of a subtree based on a given tree

Question

(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.

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

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.

Answer 1

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.

Answer 2

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.