inverting/rotating n-ary trees

[Dreikin]

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.

[dkf]

@Dreikin said in inverting/rotating n-ary 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.

[Dreikin]

@dkf said in inverting/rotating n-ary trees:

@Dreikin said in inverting/rotating n-ary 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, 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.

[Dreikin]

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