convert Binary tree to Binary Search Tree inplace using C

Question

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)

Answer 1

Perform a post-order (bottom up) traversal of the tree, taking the nodes that are visited and inserting them into a BST.

Does "without any extra space" preclude recursion?

If not, then something like:

# top level call passes null for bst
bt_to_bst (root, bst)
  # nothing to add to bst; just return it
  if null(root) -> return bst
  # if this is a leaf node, stick it into the BST
  if null(root->left) && null(root->right)
    return bst_insert(bst, root)
  # otherwise add all of left subtree into the bst and then the right tree
  bst = bt_to_bst (root->left, bst);
  return bt_to_bst (root->right, bst);

bt_to_bst is a filtering operation; it takes an existing bst and returns a new one with the given node added to it.

Adding a leaf node to the bst is safe because we will never visit it again, so we can overwrite its left and right pointers.

Answer 2

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.