Convert Binary Tree -> BST (maintaining original tree shape)

Question

I have a binary tree of some shape. I want to Convert it to BST search tree of same shape. Is it possible?

I tried methods like -

• Do In-order traversal of Binary Tree & put contents into an array. Then map this into a BST keeping in mind the condition (left val <= root <= right val). This works for some cases but faile for others.

P.S.: I had a look at this - http://stackoverflow.com/questions/741900/binary-trees-question-checking-for-similar-shape. But It's easy to compare 2 BST's for similarity in shape.

Answer 1

The method you describe is guaranteed to work if you implement it properly. The traversal order on a binary tree is unique, and defines an ordering of the elements. If you sort the elements by value and then stick them in according to that ordering, then it will always be true that

left subtree <= root <= right subtree

for every node, given that this is the order in which you traverse them, and given that you sorted them in that order.

Answer 2

The short answer is: you can't. A BST requires that the nodes follow the rule left <= current < right. In the example you linked: http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg, if you try and build a BST with the same shap you'll find that you can't.

However if you want to stretch the definition of a BST so that it allows left <= current <= right (notice that here current <= right is allowed, as apposed to the stricter definition) you can. Sort all the elements and stick them in an array. Now do an in-order traversal, replacing the values at nodes with each element in your array. Here's some pseudo code:

// t is your non-BST tree, a is an array containing the sorted elements of t, i is the current index into a
index i = 0
create_bst(Tree t, Array a)
{
  if(t is NIL)
    return;
  create_bst(t->left, a)
  t->data = a[i]
  i++
  create_bst(t->right, a)
}

The result won't be a true BST however. If you want a true BST that's as close to the original shape as possible, then you again put the elements in a sorted array but this time insert them into a BST. The order in which you insert them is defined by the sizes of the subtrees of the original tree. Here's some pseudo-code:

// left is initially set to 0
create_true_bst(Tree t, BST bt, array a, index left)
{
  index i = left + left_subtree(t)->size
  bt->insert(a[i])
  if(left_subtree(t)->size != 0)
  {
    create_true_bst(t->left, bt, a, left)
    create_true_bst(t->right, bt, a, i + 1)
  }
}

This won't guarantee that the shape is the same however.