I have created an algorithm whose purpose should be of, given two nodes A and B in a BST, it switches the roles (or positions in the tree) of the two by simply moving pointers. In my representation of a BST, I am using a double linked connection (i.e. A.parent == B and (B.left == A) or (B.right == A)). I am not sure if it's completely correct or not. I have divided the algorithm in two situations.

1. A and B are directly connected (either A is the parent of B or B the parent of A)
2. All the other cases

For each of the previous cases I have created a nested function. I would like to have your opinion on the first the correctness of the algorithms and if I can somehow then improve it. Here's the code:

```
def switch(self, x: BSTNode, y: BSTNode, search_first=False):
    if not x:
        raise ValueError("x cannot be None.")
    if not y:
        raise ValueError("y cannot be None.")
    if x == y:
        raise ValueError("x cannot be equal to y")

    if search_first:
        if not self.search(x.key) or not self.search(y.key):
            raise LookupError("x or y not found.")

    def switch_1(p, s):
        """Switches the roles of p and s,
        where p (parent) is the direct parent of s (son)."""
        assert s.parent == p

        if s.is_left_child():
            p.left = s.left
            if s.left:
                s.left.parent = p

            s.left = p

            s.right, p.right = p.right, s.right
            if s.right:
                s.right.parent = s
            if p.right:
                p.right.parent = p
        else:
            p.right = s.right
            if s.right:
                s.right.parent = p

            s.right = p

            s.left, p.left = p.left, s.left
            if s.left:
                s.left.parent = s
            if p.left:
                p.left.parent = p

        if p.parent:
            if p.is_left_child():
                p.parent.left = s 
            else:
                p.parent.right = s
        else:  # p is the root
            self.root = s

        s.parent = p.parent
        p.parent = s

    def switch_2(u, v):
        """u and v are nodes in the tree
        that are not related by a parent-son
        or a grandparent-son relantionships."""
        if not u.parent:
            self.root = v
            if v.is_left_child():
                v.parent.left = u
            else:
                v.parent.right = u
        elif not v.parent:
            self.root = u
            if u.is_left_child():
                u.parent.left = v
            else:
                u.parent.right = v
        else:  # neither u nor v is the root                
            if u.is_left_child():
                if v.is_left_child():                   
                    v.parent.left, u.parent.left = u, v
                else:
                    v.parent.right, u.parent.left = u, v
            else:
                if v.is_left_child():                   
                    v.parent.left, u.parent.right = u, v
                else:
                    v.parent.right, u.parent.right = u, v                    

        v.parent, u.parent = u.parent, v.parent
        u.left, v.left = v.left, u.left
        u.right, v.right = v.right, u.right

        if u.left:
            u.left.parent = u
        if u.right:
            u.right.parent = u
        if v.left:
            v.left.parent = v
        if v.right:
            v.right.parent = v

    if x.parent == y:
        switch_1(y, x)            
    elif y.parent == x:
        switch_1(x, y)
    else:
        switch_2(x, y)

```

I really need that `switch` works in all cases no matter which nodes `x` or `y` we choose. I have already done some tests, and it seems to work, but I am still not sure.

**EDIT**

Eventually, if it's helpful somehow, here you have the complete implementation of my BST (*with the tests I am doing*):

> 
> <https://github.com/dossan/ands/blob/master/ands/ds/BST.py>
> 
> 
> 

**EDIT 2 (just a curiosity)**

@Rishav commented:

> 
> I do not understand the intention behind this function.. if it is to swap two nodes in the BST, is it not sufficient to swap their data instead of manipulating pointers?
> 
> 
> 

I answered:

> 
> Ok, maybe I should have added a little bit more about the reason behind all this "monster" function. I can insert `BSTNode` objects or any comparable objects in my BST. When the user decides to insert any comparable object, the responsibility of creating the `BSTNode` is mine, therefore the user has no access to a initial `BSTNode` reference, unless they search for the key. But a `BSTNode` would only be returned after the insertion of the key, or there's already another `BSTNode` object in the tree with the same key (or value), but this latter case is irrelevant.
> 
> 
> The user can also insert a `BSTNode` object in the tree which has an initial (and should remain constant) key (or value). Nevertheless, if I just exchanged the values or keys of the nodes, the user would have a reference to a node with a different key then the key of the node he inserted. Of course, I want to avoid this.
> 
> 
>