Mirroring a binary tree

Question

I am trying to find the mirror image of a binary tree. Here is what I do so far:

import treetoolbox.*;

public class MirrorTree extends BinaryTree<String> {

    public MirrorTree(String key) {
        this(null, key, null);
    }

    public MirrorTree(MirrorTree left, String key, MirrorTree right) {
        this.key = key;
        this.left = left;
        this.right = right;
        root = this;
    }

    public MirrorTree mirrorSymmetricTree() {
        if (root == null) {
            return null;
        }

        final MirrorTree left = (MirrorTree) root.left;
        right = root.right;
        root.left = mirrorSymmetricTree(right);
        root.right = mirrorSymmetricTree(left);
        return (MirrorTree) root;
    }

    public static MirrorTree mirrorSymmetricTree(BinaryTree<String> t) {
        return null;
    }
}

What am I doing wrong? The problem should be in this part:

if (root == null) {
    return null;
}

final MirrorTree left = (MirrorTree) root.left;
right = root.right;
root.left = mirrorSymmetricTree(right);
root.right = mirrorSymmetricTree(left);
return (MirrorTree) root;

But I think I am missing something.

Answer 1

Assuming you are using a BinaryTree<E> similiar to this documentation

You can see live version of my solution

This is how BinaryTree<E> is built where BinaryTree<E> is the Binary-Tree node itself, and every node in the tree is a tree by itself. This is how the insert method for BinaryTree<E> looks like

public void insert(T value)
{
    if (this.value == null)
    {
        this.value = value;
        return;
    }
    else
    {
        if (this.value.compareTo(value) >= 0)
        {
            if (this.left == null)
                this.left = new BinaryTree<T>(value);
            else
                this.left.add(value);
        }
        else
        {
            if (this.right == null)
                this.right = new BinaryTree<T>(value);
            else
                this.right.add(value);
        }
    }
}

Here is how the recursive function look like

    private void mirrorSymmetricTree(MirrorTreeNode<T> m, BinaryTreeNode<T> n)
    {
        if (n == null) // base case
        {
            return;
        }

        if (n.left != null)
        {
            m.left = new MirrorTreeNode<T>(n.left.value);
            mirrorSymmetricTree(m.left, n.left);
        }

        if (n.right != null)
        {
            m.right = new MirrorTreeNode<T>(n.right.value);
            mirrorSymmetricTree(m.right, n.right);
        }
    }

    public static MirrorTree mirrorSymmetricTree(BinaryTree<T> t)
    {
        if (t == null)
        {
            return null;
        }

        if (t.root != null)
        {
            this.root = new MirrorTreeNode<T>(t.root.value);
            mirrorSymmetricTree(this.root, t.root);
        }

        return this;
    }

Where your MirrorTree node would look like this

class MirrorTreeNode<T extends Comparable<T>>
{
    public T value;
    public MirrorTreeNode<T> left;
    public MirrorTreeNode<T> right;

    public MirrorTreeNode<T> (T value)
    {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    ..
}

Then you can mirror a tree by calling mirrorSymmetricTree on a BinaryTree

BinaryTree<String> t1 = new  BinaryTree<>();
t1.addAll({"D","B","F","A","C","E","G"});

//            D
//        B       F
//      A   C   E   G

t1.printDFS();

// A, B, C, D, E, F, G

MirrorTree<String> t2 = new MirrorTree<>();
t2.mirrorSymmetricTree(t1);

// t2 is a copy of t1 now

t2.printDFS();

// A, B, C, D, E, F, G

Notes

• In order to mirror a binary tree of size N, you have to visit every node in that tree once, thus mirroring a tree has time complexity of O(N)

• In order to mirror a binary tree, the items you store has to be Comparable, meaning they can be compared to find out if this.value > input or this.value < input to decide where to put it in the tree

• In order to make sure the items are Comparable, you either implement this manually, or you demand that template type has to implement Comparable<T> interface, which force T to have compareTo function that let you compare values\keys as if they were numbers, where A.compareTo(B) > 0 is equivlant to A > B

Answer 2

Delete this function:

public static MirrorTree mirrorSymmetricTree(BinaryTree<String> t) {
    return null;
}

Add the parameter to this function to make it recursive:

public MirrorTree mirrorSymmetricTree(BinaryTree<String> t) {
    if (root == null) {
        return null;
    }

    final MirrorTree left = (MirrorTree) root.left;
    right = root.right;
    root.left = mirrorSymmetricTree(right);
    root.right = mirrorSymmetricTree(left);
    return (MirrorTree) root;
}

Answer 3

Your problem is here:

public static MirrorTree mirrorSymmetricTree(BinaryTree<String> t) {
    return null;
}

you are not doing anything in this method!