To ensure a fair and transparent recruitment process, please do not use GenAI tools during your interview unless explicitly permitted. We aim to evaluate your authentic skills, experiences and potential. Failure to adhere to these guidelines may result in disqualification from the recruitment process.

Please implement a serializer for a binary tree.

You can use whatever language you prefer; this sample code in Java is just an example.

interface CustomSerializable { byte[] serialize(); }

class BinaryTree<K implements CustomSerializable & Comparable, V implements CustomSerializable> implements CustomSerializable { BinaryTree<K,V> left; BinaryTree<K,V> right; K key; V value;

byte[] serialize() {
   // TODO: Your task today is to implement the CustomSerializable interface.
}

public BinaryTree(byte[] serialized) {
  // callers can also use this constructor to deserialize a previously-serialized tree.
}

// The usual tree methods are available.
void insert(K key, V value) { // standard binary search tree implementation }
void remove(K key); { // standard binary search tree complexity and runtime }
V get(K key); { // standard binary search tree complexity and runtime }
long size();

}

class BinaryTree:

Feel free to define left, right, etc as you like

def init(self, val) self.val = val self.left = None self.right = None

def serilaize(self, root):
    #self.val.serialize() # we can assume that this exists
    # Navigate the tree using either DFS/ BFS and get the servialized values
    self.serialized_value = []
    def dfs(node):
        if not node:
            return 0

        left = dfs(node.left)
        right = dfs(node.right)
        self.serialized_value.append(left,right) # [0,0,ser(2),0,0,ser(3),ser(4),0,0,ser(6),ser(5)]
        return node.val.serialize()

    self.serialized_value.append(dfs(root))
    return ''.join(self.serialized_value)

Serialization: O(n)

O(n + 2*K) K=leaf node

bin_tree = BinaryTree(5) bin_tree = BinaryTree().insert(4) bin_tree = BinaryTree(6) ...

'00200340065' def deserialize(bytes):

myType.Deserialize(bytes) can give us a value

if we encounter double 0's -> indicate a leaf node

take the next value as the leaf

    for b in bytes:

Siingle element Tree

5

Dfs(5) -> dfs(5.left = None) -> 0

        -> dfs(5.right = None) = -> 0
        -> dfs()

5

4 6