Binary Search Trees Switching subtrees

Question

So I'm trying to write a function that when given two pointers to nodes in the BST, will 'switch' the subtree locations.

typedef struct NODE { 
  struct NODE* parent;
  struct NODE* left;
  struct NODE* right;
}node_t;

This is the node struct I have for the BST.

My function goes along the line of :

void switch_subtree(node_t* a, node_t* b)
{
  if (a==NULL || b==NULL)
    {
      return;
    }

  if (a->parent->left == a)
  {
    a->parent->left = b;
  }
  else
  {
    a->parent->right = b;
  }

  if (b->parent->left == b)
  {
    b->parent->left = a;
  }
  else
  {
    b->parent->right = a;
  }

  nodes * temp = a;
  a->parent = b->parent;
  b->parent = temp->parent;
}

However, when I run it, it does not properly switch the subtrees.

Can anyone point out any errors Im making and point me in the right direction?

Thanks!!!

Answer 1

Your problem is here:

nodes * temp = a;
  a->parent = b->parent;
  b->parent = temp->parent;

correctly it should read:

nodes * temp = a->parent;
  a->parent = b->parent;
  b->parent = temp;

otherwise a->parent is forever lost after line 2.

rationale

wrong approach

The line temp = a will make both pointers temp and a point to the same NODE structure:

                   +- > +--------+      +- > +--------+
                   |    |        |      |    |        |     
                   |    | ...    |      |    | ...    |     
                   |    +--------+      |    +--------+
                   |                    |
                   +--------------+     +----------------+
                                  |                      |
         +--------+- > +--------+ |     +- > +---------+ |
         |        |    | parent |-+     |    | parent  |-+
         |        |    | ...    |       |    | ...     |
         |        |    +--------+       |    +---------+
         |        |                     |
+------+ |  +---+ |               +---+ |               
| temp |-+  | a |-+               | b |-+               
+------+    +---+                 +---+

Changing a->parent in line 2 (a->parent = b->parent) will also change temp->parent as both are just different names for the same component (parent) of the same NODE structure:

                       +--------+   +---+- > +--------+
                       |        |   |   |    |        |     
                       | ...    |   |   |    | ...    |     
                       +--------+   |   |    +--------+
                                    |   |
                                    |   +--------------+
                                    |                   |
         +--------+- > +--------+   |   +- > +---------+
         |        |    | parent |---+   |    | parent  |
         |        |    | ...    |       |    | ...     |
         |        |    +--------+       |    +---------+
         |        |                     |
+------+ |  +---+ |               +---+ |               
| temp |-+  | a |-+               | b |-+               
+------+    +---+                 +---+

The assignment b->parent = temp->parent doesn't change anything at all, as both b->parent and temp->parent are already pointing at the same node. - mistake !

alternative

Taking a look at the proposed alternative, temp = a->parent will leave you with the situation sketched below:

         +---------+- > +--------+      +- > +--------+
         |         |    |        |      |    |        |     
         |         |    | ...    |      |    | ...    |     
         |         |    +--------+      |    +--------+
         |         |                    |
         |         +--------------+     +----------------+
         |                        |                      |
         |        +- > +--------+ |     +- > +---------+ |
         |        |    | parent |-+     |    | parent  |-+
         |        |    | ...    |       |    | ...     |
         |        |    +--------+       |    +---------+
         |        |                     |
+------+ |  +---+ |               +---+ |               
| temp |-+  | a |-+               | b |-+               
+------+    +---+                 +---+

After a->parent = b->parent temp is still pointing to the original parent node of the node pointed to by a:

         +----------- > +--------+      +- > +--------+
         |              |        |      |    |        |     
         |              | ...    |      |    | ...    |     
         |              +--------+      |    +--------+
         |                              |
         |                        +-----+----------------+
         |                        |                      |
         |        +- > +--------+ |     +- > +---------+ |
         |        |    | parent |-+     |    | parent  |-+
         |        |    | ...    |       |    | ...     |
         |        |    +--------+       |    +---------+
         |        |                     |
+------+ |  +---+ |               +---+ |               
| temp |-+  | a |-+               | b |-+               
+------+    +---+                 +---+

Finally assigning b->parent = temp will give the node pointed to by b the right parent:

         +--------+-- > +--------+  +----- > +--------+
         |        |     |        |  |        |        |     
         |        |     | ...    |  |        | ...    |     
         |        |     +--------+  |        +--------+
         |        |                 |
         |        +-----------------|--------------------+
         |                          |                    |
         |        +- > +--------+   |   +- > +---------+ |
         |        |    | parent |---+   |    | parent  |-+
         |        |    | ...    |       |    | ...     |
         |        |    +--------+       |    +---------+
         |        |                     |
+------+ |  +---+ |               +---+ |               
| temp |-+  | a |-+               | b |-+               
+------+    +---+                 +---+