top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to convert a binary tree into binary search tree?

+4 votes
782 views

How to convert a binary tree into binary search tree keeping the structure of tree intact?

posted Oct 27, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

+1 vote

Simple approach
1) Create a temp array arr[] that stores inorder traversal of the tree. This step takes O(n) time.
2) Sort the temp array arr[]. Time complexity of this step depends upon the sorting algorithm.
3) Again do inorder traversal of tree and copy array elements to tree nodes one by one. This step takes O(n) time.

answer Oct 27, 2013 by Salil Agrawal
0 votes

Element in binary tree can be any order. smaller value can sit as bottom child, so can can nor predict that..

So, just do traverse and store the element in list.

Now, traverse the list and make a binary search tree.

We can not go with array as we do not have size of tree.

answer Oct 28, 2013 by sivanraj
Looks that you will not get the same structure if you follow this approach.
Similar Questions
+1 vote

How to balance the binary search tree in C/C++? Please provide the necessary explanation also?

+2 votes

How to find the smallest element in a Binary Tree (Not BST)? Sample C/C++ code would be helpful.

+2 votes

Please share the code or algorithm to delete a node from Threaded Binary Tree.

...