Binary Tree Serialization and Deserialization using in-order traversal

0
votes

The below is an excerpt from geeksforgeeks

If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.

Questions

  1. Is it not possible to use in-order traversal for serialization and deserialization of Binary Trees?. if so why?
  2. what is the distinction between Binary Tree and BST serialization?. the above statement is not clear about this distinction
1
algorithmserializationdeserializationb-tree
A B-Tree is a fundamentally different data structure than a Binary Tree. Please revise your question, as it doesn't make sense to mix these two terms. In addition, the only difference between a Binary Tree and a Binary Search Tree is that a BST is ordered, i.e. for any given node, its value lies in between its left and right nodes' values, e.g. Node.Left <= Node <= Node.Right. - Ondrej Tucny
@OndrejTucny thanks i have amended the question .. I understand the difference between Binary Tree and Binary search tree but what I don't understand is there any implications in how a BST is serialized?... the wording from the cited site suggests there is some subtle difference between how the two is serialized/deserialized .. - rogue-one

1 Answers

1
votes

In-order traversal of a BST produces the sorted list of data, regardless of how the tree looked like.

On the contrary, given a list produced by pre-order traversal, the BST can be reconstructed:

  • The first element is a root.

  • Split the rest by the value of the root. The S of BST guarantees that the split point exists, and the first/second slices encompass the left/right subtrees respectively.

  • Recursively apply the procedure to first and second slice.

This procedure relies heavily on the S property of BST. An arbitrary Binary Tree doesn't have the split point.