Will serialization be discretized as additional complexity?
I have a simple program to serialize a binary tree. Code:
public static <T> void serialize(TBST<T> tree, String fileName) throws FileNotFoundException, IOException {
/*
* using only 1 file will create a lot of confusion in coding.
*/
try (ObjectOutputStream oosNodeData = new ObjectOutputStream(new FileOutputStream(fileName))) {
preOrderSerialization(tree.getRoot(), oosNodeData);
}
}
private static <T> void preOrderSerialization(TBSTNode<T> node, ObjectOutputStream oosNodeData) throws IOException {
if (node == null) {
return;
}
oosNodeData.writeObject(node.element);
preOrderSerialization(node.left, oosNodeData);
preOrderSerialization(node.right, oosNodeData);
}
As we can see, the program itself does not use additional space. However, it does what it says - it serializes. What is the complexity of the space? O (n) or O (1)?
please ignore the stack space
+3
source to share
1 answer
This is essentially a recursive tree traversal and as such would be O (n). For a good overview see the following: Big-Oh for Recursive Functions
+2
source to share