R.Hull R.Hull - 7 months ago 24
Java Question

Recusively Flipping a Binary Tree

I have this homework assignment in which I need to flip a binary tree.
I'm not looking for code or anything, just hints as to why my method is not working.

Below is my code. When I step through it, it seems to work just fine, flipping each left and right node, and moving through the tree recursively.
However, it seems that on its return, it's returning a node with null left and right values, except for the original node (root).

public class TreeManipulator<E> {

public TreeManipulator() {
}

public BinaryNode<E> flipTree(BinaryNode<E> _root) {

BinaryNode<E> root = new BinaryNode<>(_root.getItem());

if (_root.getLeft() != null) {
root.setRight(new BinaryNode<>(_root.getLeft().getItem()));
this.flipTree(_root.getLeft());
}

if (_root.getRight() != null) {
root.setLeft(new BinaryNode<>(_root.getRight().getItem()));
this.flipTree(_root.getRight());
}

return root;
}
}





Here is the main method:

public static void main(String[] args) {
Integer one = 1;
Integer two = 2;
Integer three = 3;
Integer four = 4;
Integer five = 5;
Integer six = 6;
Integer seven = 7;
Integer eight = 8;

//Root Node = x
BinaryNode<Integer> x = new BinaryNode<>(one);

//X.getLeft = y
BinaryNode<Integer> y;

//X.getRight = z
BinaryNode<Integer> z;

x.setLeft(new BinaryNode<>(two));
x.getLeft().setLeft(new BinaryNode<>(six));
x.getLeft().setRight(new BinaryNode<>(seven));

x.setRight(new BinaryNode<>(three));
x.getRight().setRight(new BinaryNode<>(four));
x.getRight().setLeft(new BinaryNode<>(five));

//Set root children for easier access
z = x.getRight();
y = x.getLeft();

System.out.println(x.toStringPreorder());

//Create tree manipulator
TreeManipulator flop = new TreeManipulator();

BinaryNode<Integer> flipped = flop.flipTree(x);

System.out.println(flipped.toStringPreorder());
}


If you need the class 'BinaryNode', please ask, Ill post it, I did not want to swap the question with code...

The input:


  • Input =
    [ 1267354 ]



The expected output:


  • Original tree =
    [ 1267354 ]

  • After flip =
    [ 1345276 ]



My output:


  • After flip - '[ 132 ]'



I can't figure out why nodes '2', and '3' are returning with null left and right values.

Answer

You use the recursion wrong, flipTree doesn't flip the object you put into it, it returns a flipped copy of the original input. Even more so you don't even put that input as the child of the root, you just put a node containing only the value which is why you're only getting a tree with depth 1 as result.

This should fix the problem:

public BinaryNode<E> flipTree(BinaryNode<E> _root) {
    BinaryNode<E> root = new BinaryNode<>(_root.getItem());
    if (_root.getLeft() != null) {
        root.setRight(flipTree(_root.getLeft());
    }
    if (_root.getRight() != null) {
        root.setLeft(flipTree(_root.getRight());
    }
    return root;
}

If you do want flipTree to just flip the tree itself instead of returning a flipped version you would have to do something like this:

public void flipTree(BinaryNode<E> root) {
    BinaryNode<E> temp = root.getLeft();
    root.setLeft(root.getRight());
    root.setRight(temp);
    if (root.getLeft() != null) {
        flipTree(root.getLeft());
    }
    if (root.getRight() != null) {
        flipTree(root.getRight());
    }
}

Btw, I know you said you weren't looking for code but for hints but your original code was already so close that it is hard to give a hint without immediatly fixing the code.