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 - Binary Trees question. Checking for similar shape. But It's easy to compare 2 BST's for similarity in shape.

Answer 1

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.

Answer 2

extract all elements of tree, then sort it and then use recursive inorder process to replace values.

Answer 3

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 4

I would simply do two in-order traversals. In the first traversal, get the values from the tree and put them into a heap. In the second, get the values in order from the heap and put them into the tree. This runs in O(n·log n) time and O(n) space.