How to reconstrunct a binary tree from an array produced by preorder tree traversal

I was asked to implement a preorder tree traversal function, that function should have returned an array representing the tree, and then I was asked to implement a function to reconstruct the tree from the array my previous function returned. Something like sending a binary tree from one pc and then receiving and reconstructing it on the receiving end. The important part is that the data should only be transferred once, so I couldn't use the standard preorder and inorder combination.

In my solution, each node is printed, and then added to an array that contains all of the printed nodes, if a node doesn't have a left subtree it will print and add the letter "L", and if the tree doesn't have a right subtree it will print and add the letter "R" to the array.

That part was easy, however, I didn't know how to reconstruct the tree on the receiving side. Any help or idea will be really appreciated.

Here is what I have done for the sending part:

class TreeNode(object):
"""This class represents a tree."""

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

def send(arr_tree, data):
    print(data)
    arr_tree.append(data)

def send_sub_tree(arr_tree, node):
    send(arr_tree, node.data)
    if node.left is None:
        send(arr_tree, "L")
    else:
        send_sub_tree(arr_tree, node.left)
    if node.right is None:
        send(arr_tree, "R")
    else:
        send_sub_tree(arr_tree, node.right)

if __name__ == '__main__':
    tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, 
    TreeNode(6), TreeNode(7)))
    received_tree = []
    send_sub_tree(received_tree, tree)
    reconstructed_tree = reconstruct_tree(received_tree)

EDIT:

I have managed to implement something that kind-of works, but its messy and doesn't reconstruct the sent part perfectly:

def reconstruct_tree(arr_tree):
    node = TreeNode(arr_tree[0])
    print(node.data)

    if arr_tree[1] == "L" and arr_tree[2] == "R":
        if len(arr_tree) > 3 and arr_tree[3] != "L" and arr_tree[3] != "R":
            node.right = reconstruct_tree(arr_tree[3:])

    else:
        return node
    if arr_tree[1] != "L":
        node.left = reconstruct_tree(arr_tree[1:])
        return node

return node

Solution

Here is how you could do it. I have also moved your functions inside the class, renamed them, and made some modifications:

class TreeNode(object):
    """This class represents a tree."""
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def to_list(self):
        return [self.data] + (
                self.left.to_list() if self.left else ["L"]
            ) + (
                self.right.to_list() if self.right else ["R"]
            )
    
    @staticmethod
    def from_list(lst):
        def recurse(it):
            try:
                data = next(it)
            except StopIteration: # Only happens if list is incomplete
                return
            if data == 'L' or data == 'R':
                return
            return TreeNode(data, recurse(it), recurse(it))
        return recurse(iter(lst))

tree = TreeNode(1, 
            TreeNode(2, 
                TreeNode(4),
                TreeNode(5)
            ), 
            TreeNode(3, 
                TreeNode(6),
                TreeNode(7)
            )
        )
lst = tree.to_list()
print(lst)
# Reverse operation
recovered_tree = TreeNode.from_list(lst)
# Make that a list again to see if it is the same tree
lst2 = recovered_tree.to_list()
print(lst2) # Same as lst

Note that you could use "L" for the right-side child as well, or "R" for the left one, as the position in the array already leaves no doubt about which child is intended. One special symbol is enough.