Serialize and Deserialize a Binary Tree
Given a binary tree, how can you serialize and deserialize it?
Serialization: Storing a given tree in a file or in an array.
Deserialization: Reverse of serialization.
Serialization is done using pre-order traversal -
A pre-order traversal array is created by visiting the tree in Root Node-Left subtree-Right subtree style in recursive manner.
We write a special marker ‘-1’ whenever a null node is encountered.
--------------
For Deserialization, following algorithm is used -
int index = 0;
Node deserialize(ArrayList array)
{
if (index == array.size() || array.get(index) == -1)
{
index += 1;
return null;
}
Node root = new Node(array.get(index));
index += 1;
root.left = deserialize(array);
root.right = deserialize(array);
return root;
}
Time Complexity: O(n)
Space Complexity: O(n)
Website: http://www.ideserve.co.in
Facebook: / ideserve.co.in
In questa pagina del sito puoi guardare il video online Serialize and Deserialize a Binary Tree della durata di ore minuti seconda in buona qualità , che l'utente ha caricato IDeserve 07 maggio 2016, condividi il link con amici e conoscenti, su youtube questo video è già stato visto 33,232 volte e gli è piaciuto 456 spettatori. Buona visione!
