Reconstructing tree from a specific representation!

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

Tree_Reconstruction

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 :bear: )

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

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. https://fellows.pathrise.com/knowledge/guides/problem-serialize-and-deserialize-a-binary-tree
  2. https://leetcode.com/problems/serialize-and-deserialize-bst/
  3. https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
1 Like

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