CareerCup

Cmon...does epic ask these questions...u must be jokin..

Will this work?
Do a depth first search on the binary tree and every time a node is complete (all the children are traversed), detach that from the tree and start creating a binary search tree (insert function)

sudhakar, your approach looks vague to me. would you mind putting an example and then explain the logic you are thinking of inline with the example. thank you for your time.

For every node you found during the depth first search which has null, you can safely detach that from the current tree and use that object reference to add to a binary search tree... Every node you will be removing will always have nulls as their children because you have removed them already...

1)binary tree to doubly link list
2) sort the link list
3) again convert sorted doubly link list to bst

conmplexity: o(nlogn)

Since the question mentions it is to be done in place; we can't use another data structure.

My idea - Do a BFS using a queue. Whenever you visit a node; check left and right children. Put the middle value among them at the place of current node, smallest at the left and largest at right. (BST concept)

Do it n times so that every element would be at proper place.

Time complexity - O(n)
Space complexity - O(1)

how about doing a post order traversal. when we are at a root node, we compare the root with left and right child, put the middle value in root lesser value in left child and greater value in right child?

can we use a modified version of quick sort? use the root as pivot, and make every note in the left sub-tree less than pivot, every note in the right sub-tree greater than pivot, and recursive ..

it seems like heap sort.

Simply do a postorder traversal. While visiting each node, send its pointer to a func insert_into_bst(struct node * ptr); which takes a pointer to a node, inserts it into the bst and makes the left and right child of the node both NULL. Complexity O(nlogn)

geeksforgeeks.org/binary-tree-to-binary-search-tree-conversion/

search for binary-tree-to-binary-search-tree-conversion on google