pythonalgorithmbinary-tree

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.