I have a binary search tree in Java that holds an object at each node, the objects were added according to their name property. Which when traversed lists the objects in alphabetical order according to their name, which is good. Although, I need a method that will list the objects in descending order according to its age property. So basically I need to re-sort the tree temporarily just to print the contents in order.
What i've come up with so far is to traverse the tree and add each node to a temporary array, when that has finished the array is put through a merge sort. This works but it seems relatively inefficient and raises the complexity, this is the first binary tree i've had to create so my method is probably unnecessary.
I guess my question is, is there a more efficient way of approaching or thinking about this problem to re-sort a tree? Since the tree will be completely random (in terms of age) I can't think of another way. Any help would be greatly appreciated.
It seems that you can create another tree which is ordered based on age and whenever you add an item to the first tree, you can also add the same item to the second tree. This gives you O(logN) for insertions into the new tree and O(N) to traverse the tree and print out the items vs O(NlogN) which is the runtime for merge sort.