Day 24: Binary Tree Level Order Traversal

Day 24 — Binary Tree Level Order Traversal

Coding problem

Solution outline (coding)

• Use a queue; start with root; each level, dequeue all nodes at current depth and enqueue their children.
• Append one list of values per level to your answer.
• Optionally use a sentinel or level-size loop to separate levels.

Time complexity: O(n) — each node enqueued once.

Space complexity: O(w) — max queue width, up to n/2 in a complete tree.

from collections import deque
from typing import List, Optional


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


class Solution:
  def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
      return []
    q = deque([root])
    out = []
    while q:
      level = []
      for _ in range(len(q)):
        n = q.popleft()
        level.append(n.val)
        if n.left:
          q.append(n.left)
        if n.right:
          q.append(n.right)
      out.append(level)
    return out


# Input:  tree [3,9,20,null,null,15,7]
# Output: [[3],[9,20],[15,7]]

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).
comments(comment_id, parent_id, created_at, user_id). BigQuery: produce a level-order listing of a thread (BFS) with level numbers and sibling order for a given root comment.

Tables implied by the prompt:

• comments(comment_id, parent_id, created_at, user_id)
• thread(BFS)

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 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).

WITH RECURSIVE thread AS (
  SELECT comment_id, parent_id, created_at, user_id, 0 AS lvl, comment_id AS root_id
  FROM comments
  WHERE parent_id IS NULL
  UNION ALL
  SELECT c.comment_id, c.parent_id, c.created_at, c.user_id, t.lvl + 1, t.root_id
  FROM comments AS c
  JOIN thread AS t ON c.parent_id = t.comment_id
)
SELECT root_id, lvl, comment_id, created_at
FROM thread
WHERE root_id = @root_comment_id
ORDER BY lvl, created_at;