R.Hull - 2 years ago 84
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.

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download