Day 27: LCA of Binary Tree III

Day 27 — LCA of Binary Tree III

Coding problem

Solution outline (coding)

• Each node has a parent pointer: treat as linked lists from p and q upward.
• Like intersection of two lists: walk pointers; when one hits root, jump to the other start — second meeting is LCA.
• Or collect ancestors of p in a set, walk from q until hit.

Time complexity: O(h) — height to root.

Space complexity: O(1) for two-pointer trick; O(h) with a set.

class Node:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None
    self.parent = None


class Solution:
  def lowestCommonAncestor(self, p: Node, q: Node) -> Node:
    seen = set()
    a, b = p, q
    while a or b:
      if a:
        if a in seen:
          return a
        seen.add(a)
        a = a.parent
      if b:
        if b in seen:
          return b
        seen.add(b)
        b = b.parent
    return None


# Input:  two nodes in tree with parent pointers
# Output: their LCA

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).
org_chart(employee_id, manager_id, root_flag). BigQuery: given two employees, compute their LCA via recursive CTE and return distance to that ancestor.

Tables implied by the prompt:

• org_chart(employee_id, manager_id, root_flag)

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 Two Ptrs on Tree to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Windows: align PARTITION BY / ORDER BY with the business rule; use QUALIFY in BigQuery when you need top-N per group.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH RECURSIVE up AS (
  SELECT employee_id, manager_id, 0 AS steps FROM org_chart WHERE employee_id IN (@e1, @e2)
  UNION ALL
  SELECT o.employee_id, o.manager_id, u.steps + 1
  FROM org_chart AS o
  JOIN up AS u ON o.employee_id = u.manager_id
  WHERE o.manager_id IS NOT NULL
)
SELECT employee_id, MIN(steps) AS dist FROM up GROUP BY employee_id;