Day 25: Binary Tree Vertical Order

Day 25 — Binary Tree Vertical Order

Coding problem

Solution outline (coding)

• Assign each node a column index (root = 0, left = col-1, right = col+1) during BFS or DFS.
• Group (col, row, value) tuples; sort by column then row for vertical order.
• Use a defaultdict(list) keyed by column.

Time complexity: O(n log n) — if sorting columns; O(n) with careful bucket order.

Space complexity: O(n) — storing groups.

from typing import List, Optional, Tuple
from collections import defaultdict, deque


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


class Solution:
  def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
      return []
    colmap = defaultdict(list)
    q = deque([(root, 0)])
    lo = hi = 0
    while q:
      n, c = q.popleft()
      colmap[c].append(n.val)
      lo, hi = min(lo, c), max(hi, c)
      if n.left:
        q.append((n.left, c - 1))
      if n.right:
        q.append((n.right, c + 1))
    return [colmap[i] for i in range(lo, hi + 1)]


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

SQL interview practice

1. Interview question

Companies / track: Meta

Meta: expect event logging, ads / integrity, and social product analytics—deduping, sessionization, and window functions are frequent themes.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
events_with_coords(event_id, x, y, ts). BigQuery: group events by x-coordinate buckets and list events vertically ordered by y, simulating vertical traversal; discuss clustering choice.

Tables implied by the prompt:

• events_with_coords(event_id, x, y, ts)

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 + Hash Map 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
  DIV(x, 10) AS x_bucket,
  ARRAY_AGG(STRUCT(event_id, y, ts) ORDER BY y) AS vertical_slice
FROM events_with_coords
GROUP BY x_bucket;