Google Interview Question Developer Program Engineers
FOR i = 0; i < hightOfTree
FOR each node
IF Predecessor contains greater value in Inorder Traversal swap the values
For each node
IF Successor contains lesser value in Inorder Traversal swap the values
If the In order traversal comes out as sorted, then the BT is BST
So We can perform a inorder Morris traversal of the tree (inplace traversal), comparing the inorder predessor with current element and current element with inorder successor.
If they dont meet the order, swap them (have an indicator that the elements are swapped).
Perform this repeatedly until no swaps are required.
I tried to code the same..dint compile/test tough
#define swap_data(a,b) {int temp; temp=a->data;a->data=b->data;b->data=temp;}
typedef struct node{
struct node *left;
struct node *right;
int data;
} Node;
void convertBTtoBSTinplace(Node *root)
{
bool swapDone=true;
Node *curNode=NULL;
Node *inOrdPred=NULL;
while(swapDone) {
swapDone=false;
curNode=root;
while (curNode) {
if(curNode->left) {
inOrdPred=curNode->left;
while(inOrdPred->right && inOrdPred->right!=curNode)
inOrdPred=inOrdPred->right;
if (inOrdPred->right==curNode) {
inOrdPred->right=NULL;
if(inOrdPred->data > curNode->data) {
swap_data(inOrdPred,curNode);
swapDone=true;
}
if (curNode->right && curNode->data > curNode->right->data) {
swap_data(curNode,curNode->right);
swapDone=true;
}
curNode=curNode->right;
} else {
if(inOrdPred->data > curNode->data) {
swap_data(inOrdPred,curNode);
swapDone=true;
}
inOrdPred->right=curNode;
curNode=curNode->left;
}
} else {
if (curNode->right && curNode->data > curNode->right->data) {
swap_data(curNode,curNode->right);
swapDone=true;
}
curNode=curNode->right;
}
}
}
}
I think it works, I coded in a recursive way that seems to be clearer, and tested on some cases.
Node*
mytraversal(Node *pred, Node *curNode, int& swap) {
if(curNode == NULL)
return 0;
Node *p = mytraversal(pred, curNode->left, swap);
if(!p) p = pred;
if(p && p->value > curNode->value) {
curNode->value ^= p->value;
p->value ^= curNode->value;
curNode->value ^= p->value;
swap++;
}
p = mytraversal(curNode, curNode->right, swap);
return (p?p:curNode);
}
void
BT2BST(Node *root) {
int swap;
do {
swap = 0;
mytraversal(NULL, root, swap);
} while(swap);
}
Just like bubble sort, but it's done on a binary tree.
How about this, disassemble the old tree and assemble the new BST in pre-order.
1. Keep the original root as the new root.
2. From the current node do a pre-order traverse. Each time insert the current node into the new BST.
3. Then recursively disassemble the left tree and the right tree to insert into the new BFT.
It is inplace and preorder traverse is O(n), assambling the new BFT is O(nlogn). So, totaly time complexity is O(nlogn).
Here, the idea is to add leaf nodes to the search tree recursively. Best way is to do a post-order traversal and add your children to BST.
add_to_bst(node*& root, node* newnode)
{
if(!root) root = ptr;
else if(root->key < newnode->key)
add_to_bst(root->right, newnode);
else
add_to_bst(root->left, newnode);
}
void make_bst(node* currnode, node*& bstroot)
{
if(!currnode) return;
postorder(currnode->left);
postorder(currnode->right);
add_to_bst(bstroot, currnode->left);
add_to_bst(bstroot, currnode->right);
ptr->left = 0;
ptr->right = 0;
}
// just call
node* bt_root = input;
node* bst_root = 0;
make_bst(bt_root, bst_root);
// don't forget to add the root node to bst
add_to_bst(bst_root,bt_root);
// do a post order traversal
// at root, if left subtree's data is greater than right subtree's data, swap both subtrees
// if root data is less than left subtree's data then swap root data with left subtree's data and go on doing this untill root's data is greater than left subtree's data
// similar for right subtree
Here is the code. Recursion will have a cost O(n) worst case space complexity
// inplace conversion of a binary tree to BST
void tree_to_bst(Tree *root)
{
if( !root ||
!root->left ||
!root->right )
return;
tree_to_bst(root->left);
tree_to_bst(root->right);
// if left subtree is greater than right subtree
if(root->left && root->right && root->left->data > root->right->data)
swap<Tree*>(root->left, root->right);
// check if root is lesser than left subtrees
if(root->left && root->data < root->left->data)
{
do
{
swap<int>(root->data, root->left->data);
root = root->left;
}
while(root->left && root->data < root->left->data);
}
// check if root is greater than right subtrees
else if(root->right && root->data > root->right->data)
{
do
{
swap<int>(root->data, root->right->data);
root = root->right;
}while(root->right && root->data > root->right->data);
}
}
1. Convert the left-subtree.
2. Convert the right-subtree.
3. if(the root is lessthan its predecessor) {
swap root with its predecessor and apply heapify on it
} else if(the root is greaterthan its successor) {
swap root with its successor and apply heapify on it
} else {
//it is already a BST. Do nothing
}
Note: By Predecessor i mean the right-most node of the node's left subtree and By Successor it is the left-most node in the node's right subtree
What about converting the tree into Double link list , sort the list then make it BST ?
- Coder February 24, 2011