R.Hull - 6 months ago 8x

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

}

}

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.

Source (Stackoverflow)

Comments