CareerCup

Traverse to the value, and keep checking if the node was a right child or a left child, and once reached the code, keep adding parent to extreme right or left depending upon if node was left or right child respectively. keep returning node.

Node* makeNodeRoot(Node* root, int value) {
    if (root == NULL) return NULL;
    bool right_child = false;
    bool left_child = false;
    Node* temp;
    Node* response;
    if (value > root->getValue()) {
        right_child = true;
        response = makeNodeRoot(root->getRightNode(), value);
    } else if (value < root->getValue()) {
        left_child = true;
        response = makeNodeRoot(root->getLeftNode(), value);
    } else {
        return root;
    }
    if (response == NULL) return NULL;
    temp = response;
    cout<<"Response Value before "<<response->getValue()<<endl;
    if (right_child) {
        while(temp->getLeftNode() != NULL) 
            temp = temp->getLeftNode();
        temp->setLeftNode(root);
        root->setRightNode(NULL);
    } else if (left_child) {
        while(temp->getRightNode() != NULL) 
            temp = temp->getRightNode();
        temp->setRightNode(root);
        root->setLeftNode(NULL);
    }
    cout<<"Response Value after "<<response->getValue()<<endl;
    return response;
}

for complete solution:
gist.github.com/2930457

Traverse to the new root node.
if new root node is left/right of its parent, make left/right node of its parent NULL.
Now insert old root node into new root node, which is O(logn).

Remove the node which you want to make the root of new BST and make its parent pointer 's that child point to NULL.

After then remove one by one element from the Original BST starting from the leaves and insert them into your new BST.

Time Complexity - O(nlogn)

#include<stdio.h>
#include<stdlib.h>
typedef struct NODE
{
  int val;
  struct NODE *left;
  struct NODE *right;
}nd;
int k;
nd *node,*root=NULL;
void arrange(nd *p);
void Call(nd *q);
void insertBT(nd *p);
int preorder(nd *p);
void Display();
void main()
{
  int i=0,j;
  printf("\nEnte value");
  while(i<5)
    {
       node=(nd*)malloc(sizeof(nd));
       scanf("%d",&j);
       node->val=j;
       node->left=NULL;
       node->right=NULL;
       insertBT(node);
       i++;
    }
   Display(); 
   printf("Enter The value to be root");
   node=(nd*)malloc(sizeof(nd)); 
   scanf("%d",&j);
   node->val=j;
   node->right=NULL;
   node->left=NULL; 
   Call(node);
}


void insertBT(nd *nod)
{
   nd *temp;
   if(root==NULL)
   {
      root=nod;
   }
   else
   {
      temp=root;
      while(temp!=NULL)
      {
         if(temp->val>nod->val)
         {
            if(temp->left==NULL)
                {
                 temp->left=nod;

                // printf("%d",(temp->left)->val);
                 break;
                }
            else
                temp=temp->left;         
         }
         else
         {
            if(temp->right==NULL)
            {
              temp->right=nod;
             
              //printf("%d",(temp->right)->val);
              break;
            }
            temp=temp->right;
         }   
      }
   }
}


void Call(nd *p)
{
nd *temp;
temp=root;
root=p;
arrange(temp);
Display();
}

void arrange(nd *y)
{
nd *x,*z;
if(y!=NULL )
{
 printf("%d\n",y->val);
 x=y->left;
 z=y->right;
 y->left=NULL;
 y->right=NULL;   
 insertBT(y);
 arrange(x);
 arrange(z);
}

}
void Display()
{
  nd *y;
  y=root;
  preorder(y);
}
int preorder(nd *q)
{
  if(q==NULL)
  {
    return;
  }
  printf(" %d\n",q->val);
  preorder(q->left);
  preorder(q->right);

}

Here is a O(logn) time and O(1) space

public void changeRoot(TreeNode newRoot) {
 //the standard method remove node in BST
 removeNode(newRoot);
 
 //check root will be on the left or right side from the newRoot
 if (this.root.compareTo(newRoot) < 0)  //root stays on left
  newRoot.leftChild = root;
 else
  newRoot.rightChild = root;
 
 this.root.parent = newRoot;
 this.root = newRoot;
}