swapping nodes in binary tree

Question

I'm trying to write a function in C# that allows me to swap two nodes of a binary tree but it does not work as expected.

Here is the class with the swap method:

class Node
{
    public int value;
    public Node parent { get; set; }
    public Node left { get; set; }
    public Node right { get; set; }

    public Node addLeft(int value)
    {
        this.left = new Node(value);
        this.left.parent = this;
        this.left.left = null;
        this.left.right = null;
        return this.left;
    }

    public Node addRight(int value)
    {
        this.right = new Node(value);
        this.right.parent = this;
        this.right.left = null;
        this.right.right = null;
        return this.right;
    }

    public Node(int value)
    {
        this.value = value;
        this.parent = null;
        this.left = null;
        this.right = null;
    }

    public Node getRoot()
    {
        Node n = this;
        while(n.parent!=null)
        {
            n = n.parent;
        }
        return n;
    }

    public static void swap(ref Node n1,ref Node n2)
    {
        //updating references of n1 and n2 parents
        if(n1.Equals(n1.parent.left)) //n1 is a left child
        {
            n1.parent.left = n2;
        }
        else if(n1.Equals(n1.parent.right)) //n1 is a right child
        {
            n1.parent.right = n2;
        }
        else
        {
            throw new Exception("Something is wrong");
        }
        if (n2.Equals(n2.parent.left)) //n2 is a left child
        {
            n2.parent.left = n1;
        }
        else if (n2.Equals(n2.parent.right)) //n2 is a right child
        {
            n2.parent.right = n1;
        }
        else
        {
            throw new Exception("Something is wrong");
        }
        //updating references of n1 and n2 childs
        if(n1.left != null)
        {
            n1.left.parent = n2;
        }
        if (n1.right != null)
        {
            n1.right.parent = n2;
        }
        if (n2.left != null)
        {
            n2.left.parent = n1;
        }
        if (n2.right != null)
        {
            n2.right.parent = n1;
        }
        //Swapping n1 and n2 references
        Node t_p = n1.parent;
        Node t_l = n1.left;
        Node t_r = n1.right;
        n1.parent = n2.parent;
        n1.left = n2.left;
        n1.right = n2.right;
        n2.parent = t_p;
        n2.left = t_l;
        n2.right = t_r;

    }
}

---

And here is my main function:

    static void Main(string[] args)
    {
        Node root = new Node(10);
        Node a = root.addLeft(1);
        Node b = root.addRight(2);
        Node c = a.addLeft(3);
        Node d = a.addRight(4);
        Node e = b.addLeft(5);
        Node f = b.addRight(6);
        Node g = d.addLeft(7);
        Node h = d.addRight(8);
        Node.swap(ref a,ref d);
        Console.WriteLine("Value is: " + root.left.value);
        Console.WriteLine("Value is: " + root.left.right.value);
        Console.WriteLine("Root: " + a.getRoot().value);
        Console.WriteLine("Root: " + d.getRoot().value);
        Console.Read();
    }

---

The output of the code above is:

Value is: 4
Value is: 1

It hangs after the second Console.WriteLine and I don't understand why. Can you please tell me what am I doing wrong?

---

EDIT:

And if I try to swap the nodes multiple times, the "Something is wrong" exception is thrown.

Answer 1

while (n.parent != null)

This condition is never met so you're stuck in a while loop.

Your swap method creates a node with an infinite ancestor tree (parent). If you walk up the current node n in .getRoot() you never find a null parent.

Here is the state of the tree before we begin swapping

             ((Root(10))
            /           \
          a(1)          b(2)
         /    \        /   \
      c(3)    d(4)   e(5)  f(6)
             /    \
           g(7)   h(8)

If you swap only the child nodes for a & d, you end up with an circular reference for parent.

Something more like this for your swap method should work. I left this verbose for clarity's sake.

  public static void swap(ref Node A, ref Node B)
    {
        var newA = new Node(B.value);
        var newB = new Node(A.value);

        newA.left = A.left;
        newA.right = A.right;
        newA.parent = A.parent;

        newB.left = B.left;
        newB.right = B.right;
        newB.parent = B.parent;

        // Fix up parent node for A
        if (A.parent.left == A)
        {
            // A is a left node
            A.parent.left = newA;
        }
        if (A.parent.right == A)
        {
            // A is a Right node
            A.parent.right = newA;
        }

        // Fix up parent node for B
        if (B.parent.left == B)
        {
            // B is a left node
            B.parent.left = newB;
        }
        if (B.parent.right == B)
        {
            // B is a right node
            B.parent.right = newB;
        }


        if (newA.right == B)
        {
            // If B was a right child of A, update reference to newB
            newA.right = newB;
        }
        if (newA.left == A)
        {
            // If B was a left child of A, update reference to newB
            newA.left = newB;
        }

        if (newB.right == A)
        {
            // If A was a right child of B, update reference to newA
            newB.right = newA;
        }
        if (newB.left == A)
        {
            // If A was a left child of B, update reference to newA
            newA.left = newB;
        }

        // Update child references to be orphaned to point to new parents for A
        A.left.parent = newA;
        A.right.parent = newA;

        // Update child references to be orphaned to point to new parents for A
        B.left.parent = newB;
        B.right.parent = newB;

        // Final Swap to update ref types
        A = newA;
        B = newB;

    }

Desired State after the swap

         ((Root(10))
        /           \
      d(4)          b(2)
     /    \        /   \
  c(3)    a(1)   e(5)  f(6)
         /    \
       g(7)   h(8)

Here is some quick & dirty verification code that runs in the console. I haven't checked all possible cases, but it seems to update all the relevant nodes in this case now.

    static void Main(string[] args)
    {
        var root = new Node(10);
        var a = root.addLeft(1);
        var b = root.addRight(2);
        var c = a.addLeft(3);
        var d = a.addRight(4);
        var e = b.addLeft(5);
        var f = b.addRight(6);
        var g = d.addLeft(7);
        var h = d.addRight(8);
        Node.swap(ref a, ref d);

        if (root.left.value != 4) 
            throw new ApplicationException("New Root --> left --> value != 4 as expected");
        Console.WriteLine("New root --> left node has correct value of 4");

        if ((root.left.right.parent != root.left))
            throw new Exception("and root --> left --> right has incorrect parent");   
        Console.WriteLine("Root --> left --> right has the correct parent"); 

        if (root.left.right.value != 1)
            throw new ApplicationException("New Root --> left --> right --> value did not equal 1.");
        Console.WriteLine("New Root --> Left --> right has the correct value of 1");

        if (root.left.right.left.value != 7)
            throw new ApplicationException("New Root --> left --> right --> left --> value was not 7 as expected.");
        Console.WriteLine("New Root --> left --> right --> left.value had a value of 7 as expected");

        if (root.left.right.left.parent != root.left.right)
            throw new ApplicationException("New Root --> left --> right --> left --> parent was not root --> left --> right as expected");
        Console.WriteLine("New Root --> Left --> right --> left has the correct value of 7 and expected parent");


        Console.Read();
    }

Answer 2

If I am understanding what your swap function should be doing, it should be as simple as this:

    public static void swap(Node n1, Node n2)
    {
        Node left1 = n1.left;
        Node left2 = n2.left;
        Node right1 = n1.right;
        Node right2 = n2.right;
        Node parent1 = n1.parent;
        Node parent2 = n2.parent;

        n1.left = left2;
        n2.left = left1;

        n1.right = right2;
        n2.right = right1;

        n1.parent = parent2;
        n2.parent = parent1;
    }

What I think you need to do is simple swap n1's left and right with n2's left and right. No need for ref's either, since its a reference type and not a value type.

Answer 3

Please take a look at this line:

if (n1.right != null)
{
    n1.right.parent = n2;
}

If n2 is the right child of the n1, as in this case, n1.rightisn2, so n1.right.parent = n2 is actually n2.parent = n2 which causes the loop.

To solve the problem you have to either make copies of the nodes and then replace them, or try to do both swaps atomically and independently.