Recursively flipping a binary tree

Question

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;
    }
}

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.

Daan van der Kallen Daan van der Kallen · Accepted Answer · 2016-04-22T04:11:05

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.

Recursively flipping a binary tree

1 Answers