Sign in to follow this  
Concentrate

Mirror function for binary tree

Recommended Posts

I am thinking very hard, and came to realize that if its even possible, for the interface given below :
public interface BinaryTree<T extends Comparable<T>>   {
  public Position<T> root(); 
  public Position<T> parent(Position<T> n);
  public boolean isRoot(Position<T> n);
  public boolean isInternal(Position<T> n);
  public boolean isExternal(Position<T> n);
  public boolean isEmpty();
  Position<T> getLeft(Position<T> p);
  Position<T> getRight(Position<T> p);
  boolean hasLeft(Position<T> p);
  boolean hasRight(Position<T> p);
  Position<T> insert(T obj);
 // T remove(Position<T> p); (not necessary for now )
}
//in a new File
public interface Position<T> {
  public T element();
}

to implement a mirror function, in which it accepts a BinaryTree and returns its mirror. But the above interface does not allow me to change or swap or change anything for a Position<T>. So before I ask my prof anything, is it possible to implement this mirror function? I thought about it, and thought that maybe I could create a new Tree in a way that it is the mirror of the tree passed. But then the binary Tree, insert function inserts the lower element to the left and the greater element to the right, so that won't work. So I am running out of ideas. Any help. I ask here because my professor probably won't answer till a couple of days, since we are on break.Thanks

Share this post


Link to post
Share on other sites
Instead of reassigning "left" and "right", reassign the interpretation of which field represents "left" and which represents "right". That is, add a 'bool reversed;', and consult it in the implementation of (get|has)(Left|Right). Then to Mirror(), you just clone 'this' and toggle the flag.

Share this post


Link to post
Share on other sites
How about you post exact problem description. Mirror is a nonsensical operation anyway, and there is likely a detail that makes it possible.

For example, if the task is to print out mirrored tree, then it's trivial. If the task is to actually mirror the tree, then creating a new one is acceptable.

But if the task is to transform an existing tree, then it's likely not doable in place.

Stupid school assignments, why don't they finally either lay off this nonsense or go back to actual ADT representation which is independent of implementation. Seeing examples like this makes me realize why there is an anti-OO movement. It exposes all the flaws one encounters in real world, where round peg is hammered into square hole.

Meanwhile, any real world binary tree will either be implemented in some SQL table or it will be implemented in-place in a linear array with index encoding the parent/child relation.

Share this post


Link to post
Share on other sites
If you're making a new tree with that tree interface you need to use an inverted comparison operator to get a mirror.

I believe you could just make a new template that extends Comparable<T> and stores an existing Comparable<T> object, but returns the opposite result to it.

Share this post


Link to post
Share on other sites
Below is a brief description. The code is what I cam up with, but for now
it just copies the tree. Initially it was just a skeleton, I provided the body.


/**
* Q4. The mirror question. Feel free to add private methods as you see fit.
* @author ldm
*
* @param <T> the type of elements in the tree to mirror
*/

public class Mirror<T extends Comparable<T>> {
/**
* The mirror algorithm (build a new tree that is the mirror image of the input
* @param tree the tree to mirror
* @return the mirror of tree.
*/

public BinaryTree<T> doIt(BinaryTree<T> tree) {
BinaryTree<T> mirrorTree = new BasicBTree<T>();
_doIt(tree,tree.root(),mirrorTree);
return mirrorTree;
}
private void _doIt(BinaryTree<T> tree, Position<T> root, BinaryTree<T> newTree){
if(root == null){
return;
}
else
{
newTree.insert(root.element());
_doIt(tree,tree.getRight(root),newTree);
_doIt(tree,tree.getLeft(root),newTree);

/* Swap somehow */
}
}

}






I thought of all the suggestion provided. The problem is that we are not
allowed to change the interface, nor add extra boolean and such things like that. As you see we have to create a new tree, not mirror the input.
Do you think I can just create a private class, that reverses the toCompare
method forced in the T dataType?

Note : this "mirror" question is the same traditional question, I assume.
So there is no need for a input and output picture, unless you wan't to see it.
Thanks.

Also another note : notice that I have to do this with just the interface,
provided and thus cannot change the internal structure.

[Edited by - Concentrate on March 8, 2010 3:02:54 PM]

Share this post


Link to post
Share on other sites
I was also thinking that I might be able to extend T, the generic parameter
and just reverse the compareTo method. That would have worked, but then
I realized that I couldn't extend T, since T could be a final class like the
Integer class. Is there something similar to this that I can do? Hints would be
nice. Thanks.

Share this post


Link to post
Share on other sites
A binary tree means that each node has maximum of two children. There are many ways to construct a binary tree, but only some of them obey certain invariants with regard to intra-element ordering.

Consider a Heap which is always left aligned, changing the comparator will not affect that, hence it will not mirror the structure - and mirrored heap is invalid except in special case where deepest level is fully populated.

Reversing a comparator is also not general solution since it must hold that opposite of < is >= for all possible comparisons, which might not necessarily be true (stability of sorting algorithms comes to mind).

So unless you can manually construct nodes it is not possible simply because insert() is a black box which can do anything it chooses.

Share this post


Link to post
Share on other sites
Quote:
Original post by Concentrate
we are not
allowed to change the interface, nor add extra boolean


The boolean would be added to the implementation, not the interface. Java doesn't allow you to add fields to interfaces anyway.

And you had damn well better be allowed to add things the implmentation considering that you are being asked to implement - i.e. create - the implementation.

The only thing your mirroring code has to be able to do is initialize a tree with either BST order. And that initialization would be done in a constructor for your implementation, which, you'll note, is not specified in the interface, because Java interfaces don't specify constructors.

Or you could make Mirror into a separate class that implements the entire BinaryTree interface from scratch, except that insert() chooses a child node in the opposite way. But that's a huge amount of extra, basically pointless work.

Either way, the outside mirror() function does the same thing: find each node in the input and insert() it into the output. My bit about switching interpretation vs switching actual insertion points is actually irrelevant here, since plain cloning requires the same traversal as reversing-while-you-clone. The difference is in whether the implementation-specific logic is in insert() or in the accessors. So actually you should do it in insert() since then you're only doing it once. :)

But the point is the same: it's the implementation that decides how insert() works, not the interface. The interface only specifies what insert() does: take an object and put it in the tree. The tree implementation figures out where it goes.

You can't write mirror(BinaryTree<T>) because reversing the order requires knowing what the ordering is, and BinaryTree<T> doesn't specify the order. But you can write mirror(MyImplementationOfBinaryTree<T>) just fine.

Share this post


Link to post
Share on other sites
>> The boolean would be added to the implementation, not the interface. Java doesn't allow you to add fields to interfaces anyway

Yes that what I meant, sorry. And I assume const data is not "fields" since I think interface enables us to add const data.

>>And you had damn well better be allowed to add things the implmentation considering that you are being asked to implement - i.e. create - the implementation.


Yes, I see what you mean. But I think we are expected to just use the interface
like one would if he has just the interface to work with. I will ask my teacher
some more specifications. Thanks everyone for the assist.

Share this post


Link to post
Share on other sites
Quote:
But I think we are expected to just use the interface


What do you think "use the interface" means here?

If it means "Mirror() accepts a BinaryTree<T> and is ignorant of the implementation type", then the problem is provably impossible. To produce the mirror of a tree requires placing nodes in a controlled manner. The interface explicitly abstracts away control over the node placement.

Just talk to the professor already. There isn't any more light to be shed here as is.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this