Interview Question
Country: India
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)
Worst case complexity of instert in BST is O(n) and the new root can have O(n) children, so the complexity here is O(n^2).
#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;
}
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.
for complete solution:
- karora June 14, 2012gist.github.com/2930457