TechQ: Transfer Binary Tree From Machine A to Machine B

TechQ is new initiative of Malliks where we address algorithms, datastructure or for that matter any technical questions. If you are looking for some technical question to be addressed in TechQ section, please let us know.

TechQ: Transfer a binary tree from Machine A to Machine B. Binary tree can be any binary tree without any constraints.

Algorithm: The standard algorithm is sending the inorder and pre-order from machine A to machine B and reconstructing the tree on machine B. We know its not possible to reconstruct a tree using just a preorder traversal alone as it does not track the depth here we present the algorithm where we reconstruct the tree on machine B, using just the pre-order traversal using some additional flags which are in a way used to keep track of the depths.

Machine A sends the nodes to machine B in preorder, with one additional thing wherein we also send a null whenever the node doesn’t have either left or right child.

For example, for tree shown in the image the sequence generated will be: 2,7,2,NULL,NULL,6,5,NULL,NULL,11,NULL,NULL,5,NULL,9,4,NULL,NULL,NULL, DONE. This is modified pre-order traversal where we also send NULL whenever right or left child of node is NULL.

The pseudocode on Machine A will be like:

PUSH(node *root)

{

If(root== NULL)

{

Send(NULL);

Return;

}

Else

{

Send(root->VAL);

PUSH(root->left);

PUSH(root->right);

}

}

When we want to send a binary tree from machine A we will just call:

PUSH(root);

SEND(“DONE”);

On machine B we need to reconstruct the tree based on this sequence, before going ahead I would like to show that the sequence generated will be unique for any given tree.

1

/ \

2 3

Seq: 1,2,N,N,3,N,N,D

1

/

2

/

3

Seq: 1,2,3,N,N,N,N,D

1

/

2

\

3

Seq: 1,2,N,3,N,N,N,D

As you can see from above example its clear that no two different trees can generate the same sequence. Now we will write a pseudocode on Machine B which will PULL the nodes from machine A.

PULL(node *root)

{

Node * tmp=new node();

tmp->VAL= GetFromA();

if(tmp->VAL==”DONE”) return;

if(tmp->VAL==”NULL”) tmp=NULL;

root=tmp;

if(root!=NULL)

{

PULL(root->left);

PULL(root->right);

}

}

On Machine B when we want to pull binary tree we need to just call

Node *root=null;

PULL(root);

If you guys find any flaw in above approach, feel free to post it as comments below.