Day 50: Serialize / Deserialize Binary Tree

Day 50 — Serialize / Deserialize Binary Tree

Coding problem

Solution outline (coding)

• Preorder: serialize as val,null,null style with null markers for missing children.
• BFS: level order with explicit nulls; deserialize with a queue rebuilding tree.
• Ensure round-trip matches LeetCode format.

Time complexity: O(n).

Space complexity: O(n) — string or queue storage.

from typing import Optional


class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right


class Codec:
  def serialize(self, root: Optional[TreeNode]) -> str:
    out = []

    def dfs(n: Optional[TreeNode]) -> None:
      if not n:
        out.append('N')
        return
      out.append(str(n.val))
      dfs(n.left)
      dfs(n.right)

    dfs(root)
    return ','.join(out)

  def deserialize(self, data: str) -> Optional[TreeNode]:
    vals = iter(data.split(','))

    def dfs() -> Optional[TreeNode]:
      v = next(vals)
      if v == 'N':
        return None
      n = TreeNode(int(v))
      n.left = dfs()
      n.right = dfs()
      return n

    return dfs()


# Input:  tree [1,2,3,null,null,4,5]
# Output: serialize then deserialize reconstructs same shape

SQL interview practice

1. Interview question

Companies / track: Meta, Google

Meta and Google both lean on ads and product surfaces: event streams, CTR-style rates, windowed metrics, and careful handling of identity joins.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta, Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
json_trees(doc_id, json_blob). BigQuery: parse JSON trees to adjacency lists and serialize/deserialize between nested JSON and normalized tables.

Tables implied by the prompt:

• json_trees(doc_id, json_blob)

Engine: BigQuery — use its date, array, and approximate functions as documented.

2. Solution outline

• Clarify out loud: result grain (one row per what?), join keys, time zone, and any ORDER BY / LIMIT / tie-breakers.
• Map BFS / DFS to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT doc_id,
  JSON_QUERY_ARRAY(json_blob, '$.children') AS children
FROM json_trees;