# Linear Python solution with sparse heap array representation

• We use the canonical index trick for heaps, which map the left and right
children to indexes 2i and 2i+1, respectively (we shift one place to the
right, in order to start indexing at 0).

Since the heap representation is good for full-trees, we would need
exponential space to fulfill it; assuming that we can potentially find thin
trees, we opt to use an sparse representation for the array. We serialize the
list of (index,value) pairs. Actually, the array is represented in memory as
a dictionary.

Space complexity is O(n), due both the array representation and the
auxiliary stack we use DFS traversal. Time should be O(n) as well due DFS.

``````class Codec:
def serialize(self, root):
arr = dict()
if not root:
return ""
stack = [(root, 0)]
while stack:
node, i = stack.pop()
arr[i] = node.val
for child, j in ((node.left, 2 * i + 1), (node.right, 2 * i + 2)):
if child:
arr[j] = child.val
stack.append((child, j))
ser = ""
for i, v in arr.iteritems():
ser += ("," if i > 0 else "") + str(i) + ":" + str(v)
return ser

def deserialize(self, data):
if not data:
return None
parse_pair = lambda p: tuple(map(int, p.split(":")))
arr = dict([parse_pair(p) for p in data.split(",")])
root = TreeNode(arr[0])
stack = [(root, 0)]
def getpush_child(j):
child = None
if j in arr:
child = TreeNode(arr[j])
stack.append((child, j))
return child
while stack:
node, i = stack.pop()
node.left = getpush_child(2 * i + 1)
node.right = getpush_child(2 * i + 2)
return root
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.