Questions

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Leetcode

I/P:
            1
        2       3  
            4       5

O/P:   [1,2,3,null,null,4,5]

We need to traverse the tree in a traversal order and capture the nodes. We also need to make sure that the traversal order we pick helps us find the root from the serialized string. We can use preorder, which means the root will always be the first element in the serialized string.

Now, how to deserialize from the string?

For preorder, we know the traversal order is root - left - right, so if we reverse-engineer, we know we will get the root first. The very next element would be its left child, the very next element would be its right child and so on. We can use that property to recursively re-construct the tree.

Implementation: SerializeDeserialize

Time complexity

O(n)

Space complexity

O(n)

Space optimizations

For a skewed tree, our serialized string looks like 1,null,2,null,3,null,null. One quick optimization we can do is remove all the tail null's. Why? Because if we reach the end of our LinkedList, we are going to return null's anyway.

Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Leetcode

root:
        3
    4       5   
1       2

subroot:
        4
    1       2

Output: true



root:
        3
    4       5   
1       2
    0

subroot:
        4
    1       2

Output: false

The subtree needs to start from a node in the tree. So first we need to find the node. Once we find the node, we need to make sure the tree is the same, including, the leaf nodes.

Implementation: Subtree

Time complexity

O(n)

Space complexity

The recursion stack, at most, will extend to all nodes of the tree. O(n)

Return to Index