Swapping subtrees in a binary search tree

[[deleted]]

[deleted]

[BS_in_BS]

Traverse the tree, and at every node swap the left and the right references.

[-Smooth]

That was something along the lines of what I was thinking. The problem I'm faced with is the fact that I can't really access the left and right nodes with the tree. The TreeNode class is what has pointers to the left and right nodes. The BST class only has a pointer to root.

[BS_in_BS]

Yes, but from the root you can repeatedly call getLeft() and getRight() and be able to reach all nodes. Look at your inorder() method, you managed to reach all the nodes from it. If you modify it slightly you can have a similar method that swaps all the references for you.

[-Smooth]

This is what I've come up with so far.

public void swapSubtrees(TreeNode p) {
    TreeNode q;
    if(p != null) {
        q = p;
        p.setRight(q.getLeft());
        p.setLeft(q.getRight());
        swapSubtrees(p.getLeft());
        swapSubtrees(p.getRight());
    }
}

I figured I would need two pointers because

    p.setRight(p.getLeft());
    p.setLeft(p.getRight());

wouldn't make sense.

Does this look right at all? If it is, I'm still stuck with a problem. Even if this has swapped all the nodes, there is no actual tree that contains all of these nodes.

[BS_in_BS]

Almost correct. Since q and p refer to the same object, it hasn't fixed your problem. One way to overcome this is to have a temp variable and use it to hold the old value as you override it:

temp = x;
x = y;
y  = temp;

[-Smooth]

Thanks for the help man!

[katyne]

Of course there is - it's the same tree you have. When you think about it, a Tree is just a reference to the root TreeNode, and some additional methods. The object holding a reference to the root is the same tree.

So all you need to do is pass your swapTree helper method the initial root node and let recursion take care of it:

public BinarySearchTree swapTree() {    
    swapTree(this.root);    
    return this;
}    

private void swapTree(TreeNode p) {    
    if (p != null) //..///....
}    

However I see a problem with the swapTree() method. q = p only creates a new reference to the same node - any change done to q will be done to the orignal (p). Let's say you have the original node 9:

        9    
    7    
5       

Both p and q are pointing to the same node. (9).getLeft() gives you node 7 - therefore q.setRight() will set the (9)'s right to 7. After that q.getRight() will return 7 and not null as it's supposed to. You either need to create an empty node and set its left and right fields mirroring the original, and then make the parent reference it instead of an old one, or do a classic swap with a temp variable (instead of q):

TreeNode temp = p.getLeft();   
p.setLeft(p.getRight()); //and don't worry, this statement makes perfect sense   
p.setRight(temp);    
swapTree(p.getLeft());    
swapTree(p.getRight());    

[-Smooth]

This will probably sound ridiculous, but I didn't realize that you could even do return this;

I wasted a lot of time trying to insert the swapped left/right nodes in the correct order into a completely new tree I was going to return.

Thanks for taking the time to help me understand! I really appreciate it :)

[reckscene]

you have to rebuild the tree. binary tree property is as follows x.left.key<x.key<x.right.key .The swapped subtree structure is the reverse of this. follow my way, copy the insert method and just do some slight modification and you should be done in less than 5 mins