# inverting/rotating n-ary 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 well-designed 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 n-ary 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 each `Node<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, and
• `direction`, 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 n-ary 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.

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

• 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, more-or-less. 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.)

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.