How do you write insert(x) when there have been lazy deletions?

• If x was deleted, but its node is still in the tree and marked deleted, You can simply remove the deleted mark. Otherwise, simply insert as usual. Let's call that lazy insertion.
• But there are other ways to insert to reuse the space of nodes that are marked as deleted.
• Given the input file Example 3 there are different outputs, depending on this choice.
• Output for Example 3 using lazy insertion
• Output for Example 3 using a space-saving form of insertion
• Note that, in either case, you still have a valid binary search tree, as indicated by the fact that the inorder lists are the same.