Algorithm to change order of tree

Question

I'm looking for an algorithm name to change the order of the levels of a tree. I've done something that works but there's a lot of code and the $ O(n) $ is very bad.

Here's an example, let say there are 3 levels. Each level representing something in a hierarchy project > budget > fiscal year

project = {a} budget = {b, c} fiscal year = {d, e}

 root
 |
 a
 / \
 b c
 /\ /\
d e d e

I would like to build a tree with the level in different order

fiscal year> project> budget

 root
 / \
 d e
 | |
 a a
 /\ /\
 b c b c

budget> fiscal year> project

 root
 / \
 b c
 /\ /\
 d e d e
 | | | |
 a a a a

The initial tree can be more complicated. Each node can have more than 2 children.

 root
 / \
 a b - Projects {a, b}
 / \ / \
 c d c e - Budgets {c, d, e}
 | | /\ |
 f g f g g - Fiscal year with data {f, g}

• Optidad: Just build the list of all possible tuples (Project, Budget, Fisc. Yr). This let you build any hierarchy tree you want in $O(N)$.
• 喜欢算法和数学: Have you considered mimicking a relation database?
• the_lotus: @Apass.Jack the content is already in a relational database. The order of the level is customization and found it easier to do outside of the database. Unless there something I didn't know about.
• 喜欢算法和数学: @the_lotus "the content is already in a relational database." What is that content in that relational database? What is in a relational database is usually very different from a tree, the input given in the post.
• the_lotus: @Apass.Jack it is, there's a list of projects, each project have different type of budgets and each budgets have money for different fiscal year.

Answer 1

If I may elaborate on @Optidad 's comment.

Input:

 root
 |
 a
 / \
 b c
 /\ /\
d e d e

"Building the list of all possible tuplets" means, in other words, enumerating all max length paths, namely:

 0 1 2
 -----
 a b d
 a b e
 a c d
 a c e

Shuffle the columns (representing the levels of the original tree) as you want, e.g.:

 2 0 1
 -----
 d a b
 e a b
 d a c
 e a c

Taking this data record by record, the desired tree can be built directly.

Output:

 root
 / \
 d e
 | |
 a a
 /\ /\
b c b c

Answer 2

I would write a function to fill a new tree one record at a time, each record being percolated down by levels. (There will be as many such functions as different orderings that you want to handle.)

Then traverse the existing tree to extract all records and feed them to the filling function.

E.g., if you retrieve the records in the order abd, abe, acd, ace, you will feed dab, eab, dac, eac, giving the partial trees

r - d - a - b
r + d - a - b
 - e - a - b
r + d - a + b
 - c
 - e - a - b
r + d - a + b
 | - c
 - e - a + b
 - c

You said nothing about your representation of the tree nodes, so this is up to you. Anyway, consider my remark below your post.