A friend of mine asked me about the ways a binary search tree (BST henceforth) could be transferred over the network. There are many ways to do so but I found one approach worth discussing here. BST can be serialized by  storing the BST in pre-order or in-order sequence and then wired over the network and then reconstructed by deserializing the sequence. Deserialization from a pre-order sequence is pretty straight forward but deserializing a in-order sequence in to BST is worth a blog post, so I decided to post it here.  I have been spending some time with Python for sometime so decided to give a try (The fact is that I find Python to be really cool).

DISCLAIMER: I am not a Python expert, so please do not expect perfect pythonic code here :)

It is being assumed that an in-order sequence will be given as input to be de-serialized.

Defined a class TreeNode to capture a  properties of tree node.

class TreeNode():

def __init__(self, val):
          self.val = val
          self.left = None
          self.right = None

We can use famous Divide and Conquer philosophy to solve this problem by building first the left sub-tree, then right-subtree and then combining the two to create the complete tree. Here is the recursive function.

def build_tree(sequence, low, high):
        if low > high:

return None
        if low == high:
                  return TreeNode(sequence[low])
        mid = (low + high)/2
        node = TreeNode(sequence[mid])
        node.left = build_tree(sequence, low, mid -1)
        node.right = build_tree(sequence, mid + 1, high)
        return node

Recursive function to print the content of the tree in in-order sequence.

def traverse(node):
        if not node:
           return
        traverse(node.left)
        print node.val,
        traverse(node.right)

Finally lets test out the code with following inorder sequence. Currently, we do not check if the input sequence if indeed a sorted sequence or not.

if __name__ == "__main__":
         sequence = [8, 10, 11, 12, 14, 18, 20]
        tree = build_tree(sequence, 0, len(sequence) -1)
        traverse(tree)