inverting/rotating nary trees

Okay, so for some reason or another (some post here mentioned it) I looked up what "inverting a binary tree" means. I haven't actually read anything beyond the definition of the challenge yet, which was this one from here:
The inverse of an empty tree is the empty tree. The inverse of a tree with root rr, and subtrees right and left, is a tree with root rr, whose right subtree is the inverse of left, and whose left subtree is the inverse of right.
So given that challenge, I though to myself "isn't inverting a welldesigned binary tree O(1)?" Then I expanded a bit, and thinking of inversion as rotation and/or change in direction, I came up with something like:
Given an nary tree with the following structure:
public partial class Node<T> { public T value public Node<T> parent { get; set; } public Node<T>[] children { get; } // Root element has null parent public Node(int dimensions) { this.parent = null; this.children = new Node<T>[dimensions]; } public Node(Node<T> parent, int dimensions) { this.parent = parent; this.children = new Node<T>[dimensions]; } } public partial class NAryTree<T> where T : IComparable { public int dimensions { get; } private Node<T> root { get; set; } public NAryTree(int dimensions) { this.dimensions = dimensions; this.root = null; } }
Then one can treat inversion of the tree as a property of how one navigates the
children
array of eachNode<T>
(which is treated like a loop), and formulate the tree operations to account for the rotation in use. Only two properties need to be added:offset
, with 0 being the default, anddirection
, represented as ±1.
These two properties can be combined into one property as a signed integer, or kept separate.
For example, iterating through a
children
array would look like:for (int i = 0; i < dimensions; i++) { int index = (offset + direction * i) % dimensions; if (node.children[index] != null) { DoSomething(node.children[index]); } }
(Note: I'm assuming
%
works as expected. Vary as necessary.)Because only these two properties need to change, inversions of such nary trees are O(1).
Now why is this in "Coding Help"? Because I want to know if is right or if I'm missing something. All the solutions I've seen on a quick Google search do the "switch every
Node<T>
's children around" approach.

@Dreikin said in inverting/rotating nary trees:
Because I want to know if is right or if I'm missing something.
Why are you exposing the list of children as an array? If you just exposed a way to iterate over them, you would be able to lock the complexity away inside.

@dkf said in inverting/rotating nary trees:
@Dreikin said in inverting/rotating nary trees:
Because I want to know if is right or if I'm missing something.
Why are you exposing the list of children as an array? If you just exposed a way to iterate over them, you would be able to lock the complexity away inside.
Laziness, moreorless. In this model, the nodes aren't (supposed) to be publicly accessible (despite the access modifier) and instead only worked with through the Tree class. I probably should have made them an inner class of the Tree given that, I guess.

Thinking about it, any arbitrary reordering of the axes ought to be O(n) where n is the number of dimensions:
public partial class NAryTree<T> where T : IComparable { class Node { public T value public Node parent { get; set; } public Node[] children { get; } // Root element has null parent public Node(int dimensions) { this.parent = null; this.children = new Node[dimensions]; } public Node(Node parent, int dimensions) { this.parent = parent; this.children = new Node[dimensions]; } } public int dimensions { get; } private Node root { get; set; } private int[] ordering { get; set; } public NAryTree(int dimensions) { this.dimensions = dimensions; this.root = null; this.ordering = new int[dimensions]; for (int i = 0; i < dimensions; i++) { ordering[i] = i; } } private void PrintChildren(Node node) { foreach (var index in ordering) { PrintNode(node.children[index]); } } private void PrintNode(Node node) { Console.WriteLine(node.value); } }
(I'm assuming insertion and balancing and other similar operations where the user of the tree doesn't see evidence of the ordering don't bother with the reordered index  they just treat it like normal. Rotations/Inversions are just views on the tree  they shouldn't affect the internal structure of it.)