CareerCup

something like heapsort or what?

BST?

Its Heap sort

I think that they are looking for in-order as opposed to post-order. Something like this:

void printInOrder(Nameval *nvp) {
if (nvp == NULL) return;
printInOrder(nvp->left);
printf("nvp = %p, name = %s, val = %d\n", nvp, nvp->name, nvp->val);
printInOrder(nvp->right);
}

Inorder traversal sequence (left, root, right); this produces a sorted sequence

any thing better then heap sort guys?

Convert BT in to singly or doubly Linked list it will take O(N) time & O(1) Time
sort linked list it will take O(nlogn) time & O(1) space & coding this is not typical task...:)

Correct me if i am wrong

Shashank

Maybe just traverse the whole tree, put them into array and sort them.

even if this is bst.how to do heapsort on bst? i mean we need indexes for heapify function.isn't it?

convert Binary Tree to BST -> do inorder traversal.
better than creating a heap i guess

complexity O(n log(n)) depends on how balance your BST is though.

Rearrange nodes to form a heap . O(n)
Delete min - O(nlogn)
So complexity O(nLogn)

Cant we do this?

Traverse through the binary tree and add each of the nodes to a Heap.
Print the Heap and it does it automatically in sorted order..

Does this idea work?

Oops.. sorry I meant Hash and not Heap..
but this will not work if there are nodes with a same value..

I think the question needs simply understand the binary tree

void printbinarytree
(
struct treenode * root
)
{
if (root)
{
printbinarytree(root->leftchild);
printf("%s\n", root->name);
printbinarytree(root->rightchild);
}
}