Serialize and Deserialize a Binary Tree

Опубликовано: 07 Май 2016
на канале: IDeserve

33,232

456

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

На этой странице сайта вы можете посмотреть видео онлайн Serialize and Deserialize a Binary Tree длительностью часов минут секунд в хорошем качестве, которое загрузил пользователь IDeserve 07 Май 2016, поделитесь ссылкой с друзьями и знакомыми, на youtube это видео уже посмотрели 33,232 раз и оно понравилось 456 зрителям. Приятного просмотра!

787