Amazon Interview Question
Country: United States
If you want to maintain the structure of the Tree do the following..
1) Perform any traversal on the Binary tree and store the elements in array.
2) Sort the array.
3) Do a inorder traversal and copy the elements in the array to the tree..
This will create a BST maintaining the structure of the tree..
Complexity : O(n log n) - sorting.
There are two ways of doing this. If memory is not an issue, traverse the tree, put all elements into an array, sort and then put the elements into a BST. If memory is a little constrained, add all elements into the BST directly. Both approaches are in O(nlogn) but the former should be a bit faster and the BST could be made balanced without self-balancing. O(nlogn) should be the best complexity for this question as well.
A binary search tree already has the property that an in-order traversal will give elements in sorted order.
- DevGuy February 19, 2014So, all we need to do here is to take the given binary tree and convert it into a BST. Do a DFS or BFS of given binary tree, and for each node encountered place them into the new BST.