Search code examples
cbinary-treebinary-search-treein-place

convert Binary tree to Binary Search Tree inplace using C

Without using any extra space convert Binary Tree to Binary Search tree.I came up with the following algo but It doesn't work.

BTtoBST(node *root)

1.if the root is NULL return

2.else current=root

3.if (current->left > current) swap(current->left , current)

4.if (current->right < current) swap(current->right , current)

5.current=current->left

6 go to 3 if current!=NULL else go to 4

7.current=current->right

Thanks in advance

PS:I saw this link but was not of much help!! Convert Binary Tree -> BST (maintaining original tree shape)

Solution

  • You can swap the nodes including subtrees (not only the node content) like in an AVL Tree http://en.wikipedia.org/wiki/AVL_tree

    Just keep swapping as long as BST constraints are violated, restarting deep first search from root after each swap.