Splitting a binary search tree at a given node

22, Feb 2011
Given a node and root of tree, how to split the binary search tree into two different trees.

The idea is to walk down the tree till the node, and keep track of the path. Climb up the tree and separate the nodes into two different trees. The algorithm is simple.

split(z, T)
   x = z.left
   y = z.right


   splitter = z


   while(z.p is valid)
     if(z.p.left = z) // z is on left of its parent
        z = z.p
        z.left = y
        y.p = z
        y = z
     else             // z is on right of its parent
        z = z.p
        z.right = x
        x.p = z
        x = z


   // add splitter if required or delete it
   insert(splitter,x)


   x.p = nil
   y.p = nil


   return x and y as two split trees.

Understanding the algorithm will be simple, if we can draw a tree and its walking as per above pseudo code.