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
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.