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)

Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

                3
        9                20
                15              7

Input: root = [3,9,20,null,null,15,7]
Output: 3

            1
                2

Input: root = [1,null,2]
Output: 2

Implementation: MaxDepthBinaryTree

The question is to find the height of the tree. To do that, we need to see which branch (left or right) has the maximum depth on each node. As we bubble up, the height at the root should tell us the maximum height.

Time complexity

O(h)

Space complexity

O(h) in the worst case

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

        1
    2       3

        1
    2       3

Input: p = [1,2,3], q = [1,2,3]
Output: true

        1
    2
        1
            2
Input: p = [1,2], q = [1,null,2]
Output: false

        1
    2       1
        1
    1       2
Input: p = [1,2,1], q = [1,1,2]
Output: false

Implementation: SameTree

There are two things to look for here: structure and value. One way to approach this problem would be to do one of the traversals and compare the results. However, if there's a mismatch early enough, we would be traversing the whole trees for no reason. While the asymptotic complexities won't change, we can cut-off computation early enough if there's a mismatch.

So, we start traversing in any order and compare the values. The only thing we need to make sure is that both the traversals are following the same traversal order.

Time complexity

O(n)

Space complexity

O(n), worst case

Return to Index