## Interview Question

Country: India

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

What if there are identical keys?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

We can use some self-balancing trees such as AVL.
It will use log n for balancing.

Hence time complexity would be n log n in worst case

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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);``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.