# Reconstructing tree from a specific representation!

If given a serialized representation of a binary tree how do you reconstruct it efficiently?
For example:

inputs to the function are a string and list of elements:For e.g:
reconstruct( “1010011”, [a,b,c,d]) should return the root node (with a) of above tree

I am trying to understand the serialized representation. Is it given to us in a level order fashion?

Yeah, it is basically a BFS representation! Level order is the correct word I presume!

So if I understand this correctly, you don’t really need the list of elements, since every time you encounter a 1, it represents a new character.
Then in the array a 0 represents a `None` node. And using the array indices, we can come up with a relation for node and it’s children, which is: `for node at index [i]: left-child = (2*i)+1 , right-child = (2*i) +2`

1 Like

Cool, that’s a great observation! But how do you recreate the tree?

Here’s one possible implementation: (first iteration, rough code )

Go through the serialized input, populating the children (using the index rules), and store their reference in a map . Note: This solution doesn’t account for invalid input .

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

def deserialize(input):
cur_char = 'a'
root = None

if input[0]=='0': # Tree rooted at a None node
return None

index_node_map = {} # maps index to a TreeNode

for index, val in enumerate(input):
if val=='0':
continue # found a None node, continue to next index

if index==0: # init root
root = TreeNode(cur_char)
index_node_map[0] = root
cur_char = chr(ord(cur_char)+1)

cur_node = index_node_map[index]

if 2*index+1 < len(input) and input[2*index+1]=='1': # init left node
left_node = TreeNode(cur_char)
cur_char = chr(ord(cur_char)+1)
index_node_map[2*index+1] = left_node
else:
left_node = None
index_node_map[2*index+1] = None

if 2*index+2 < len(input) and input[2*index+2]=='1': # init right node
right_node = TreeNode(cur_char)
cur_char = chr(ord(cur_char)+1)
index_node_map[2*index+2] = right_node
else:
right_node = None
index_node_map[2*index+2] = None

cur_node.left = left_node
cur_node.right = right_node

return root

def inorder(root):
if not root:
return None

inorder(root.left)
print(root.val)
inorder(root.right)

input = "1010011"

new_root = deserialize(input)
inorder(new_root) # outputs "acbd"
``````

You might also want to checkout the question: serialize and deserialize Binary Tree (and BST).

Related:

1 Like

Lovely, will checkout the related questions as well. Thank you!