Returning a sorted subset of items in a binary tree

Question

I have a lot of nodes stored in a binary tree in the usual fashion so that they are ordered according to some value that is stored in each node; that is, one can recurse through the tree from left to right and get the total set in sorted order.

However I have a large separate array of pointers to a subset of the nodes that are in the tree and the order in this array is random.

I would like to be able to rapidly sort this array. Is there some way to refer back to the binary tree structure to make this faster? I could add members to any of the nodes if necessary.

Thanks!

Answer 1

By adding a flag in the nodes you could get the runtime to O(t+a) (t is size of the tree and a is the size of the array). This is done by first setting the flags in the array then traversing the tree and picking out the values that were flagged.

This is only advantageous if your tree is only log a times bigger than the array. If t>>a quicksort would definitely be the preferred method as it has a runtime of O(a * log a).