General tree to Binary tree conversion complexity

Question

What is the time and space complexity of converting a general tree to binary one?!

Thanks

Answer 1

I don't know what you mean by "general tree." Regardless, the tome complexity of insertion into a balanced binary tree is O(log n), where n is the number of items currently in the tree, so building a complete tree from some list of items would be O(n log n), where n is the total number of items to be inserted.

You'll also have to include the time required to get items from the other tree. That time depends on the type of tree you have. For sake of argument I'll assume that you can traverse it in linear time, so getting data from the existing tree is O(n).

That makes your total time complexity O(n + (n log n)).

Extra space required will be n * sizeof(node), where sizeof(node) is the size of your binary tree node. Note that, if the items being stored in the "general tree" nodes are pointers, you won't have to pay the cost of copying the actual objects--just the overhead of the binary tree node, which is typically three pointers: the data, the left child link, and the right child link.